数据结构和算法入门

public static int find(int[] array, int aim) {
    // 初始化left = 最左侧, right = 最右侧
    int left = 0;
    int right = array.length - 1;
    // 当left > right则表示遍历完成
    while (left <= right) {
        // 获取中间的值
        int middle = (left + right) / 2;
        int middleValue = array[middle];
        if (middleValue == aim) {
            // 已经找到目标
            return middle;
        } else if (middleValue < aim) {
            // 目标在middle的右侧，重置left
            left = middle + 1;
        } else {
            // 目标在middle的左侧，重置right
            right = middle - 1;
        }
    }
    return -1;
}

str1.compareTo(str2)

import java.util.ArrayList;
import java.util.Comparator;

public class Address {

  public static int find(ArrayList<String> array, String aim) {
    // 初始化left = 最左侧, right = 最右侧
    int left = 0;
    int right = array.size();
    // 当left > right则表示遍历完成
    while (left <= right) {
      // 获取中间的值
      int middle = (left + right) / 2;
      String middleValue = array.get(middle);
      if (middleValue.equals(aim)) {
        // 已经找到目标
        return middle;
      } else if (middleValue.compareTo(aim) > 0) {
        // 目标在middle的左侧，重置right
        right = middle - 1;
      } else {
        // 目标在middle的右侧，重置left
        left = middle + 1;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    ArrayList<String> array = new ArrayList<>();
    array.add("Allen");
    array.add("Emma");
    array.add("James");
    array.add("Jeanne");
    array.add("Kelly");
    array.add("Kevin");
    array.add("Mary");
    array.add("Natasha");
    array.add("Olivia");
    array.add("Rose");

    int result1 = find(array, "Kelly");
    if (result1 == -1) {
      System.out.println("Kelly 不存在名单中");
    } else {
      System.out.println("Kelly 存在名单中，位置是 " + result1);
    }

    int result2 = find(array, "Edith");
    if (result2 == -1) {
      System.out.println("Edith 不存在名单中");
    } else {
      System.out.println("Edith 存在名单中，位置是 " + result2);
    }
  }
}

数字数组为：[0, 8, 2, 3, 5, 6, 2, 2, 10, 8]

重复数字为：[8, 2]

public static ArrayList<Integer> repeat(int[] array) {
    ArrayList<Integer> result = new ArrayList<>();
    for(int i = 0; i < array.length; i++){
        // 以此判断i位置元素和后面j位置元素是否相等
        for(int j = i + 1; j < array.length; j++){
            if(array[i] == array[j]){
                // 如果之前result没有，则进行添加
                if(!result.contains(array[i])){
                    result.add(array[i]);
                }
            }
        }
    }
    return result;
}

exists[0] = 1

exists[8] = 1

public static ArrayList<Integer> repeat(int[] array) {
    ArrayList<Integer> result = new ArrayList<>();
    int[] exists = new int[11];
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        // 只有当前位置已经为1，标示重复，并且输出，>1情况则不输出了
        if (exists[value] == 1) {
            result.add(value);
        }
        // 用exists标示记录
        exists[value]++;
    }
    return result;
}

数组

计算机内存管理

计算机的程序都是运行在内存中。

内存的工作原理

我们可以简单的将内存当做寄存柜。假设我们去游泳，需要将东西先寄存起来，寄存处有几个大箱子，每个箱子都有很多抽屉。

每个抽屉里可以放一样东西，如果你有 4 样东西，就需要放在 4 个抽屉里。 每个抽屉都有自己的编号，方便你查找和记录。 接下来，你就去游泳了，当你结束的时候，再将 4 个抽屉里面的东西带走。

这其实就是计算机内存的工作原理。

每个抽屉都可以当做内存的一个存储单元，而抽屉编号可以当做每个存储单元的内存地址。

为什么连续两个方格内存地址差 8？

因为我们现在电脑基本是 64 位，64 位表示内存存储最小使用单位为64个bit，也就是8个byte。

数组 - 存储和读取

为什么数组的索引从 0 开始？

数组是计算机中最基础的数据结构，每个编程语言中基本都有数组。

数组存储

要回答上面这个问题，首先得明白数组到底是怎么在内存中存储的。

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

• 线性数据结构：表示数组中数据都是按前后这种线性顺序排列的。 
• 相同数据类型：数组中的每个值的数据类型都相同。

连续内存空间

举个生活中的例子，现在有 4 个人去电影院看电影，希望坐靠前的位置并挨着坐在一排

那如果变成 5 个人了呢？那就选择第三排。

如果把每个座位当做一块内存空间，那边连续位置就相当于数组的连续内存空间。

数组读取

理解了数组的内存存储，接下来看看如何获取数组某个索引下的值？

每个数组都有对应的内存地址，将其称作为数组开始地址 --- start_address。

数组在定义的时候已经确定每个数组元素的数据类型，也就是知道每个元素需要的内存空间大小，称为 --- item_size。

那么数组里每个元素内存地址s都能被计算出来：

// 第一个元素地址
start_address

// 第二个元素地址
start_address + item_size * 1

// 第三个元素地址
start_address + item_size * 2

第 N 个元素地址公式如下:

// 第N个元素地址
start_address + item_size * (N - 1)

从这个公式可以得到两点信息：

• 数组的索引访问的时间复杂度是O(1)
• 内存地址的计算规则决定开始地址为start_address + item_size * 0，在计算机中为了方便位置的计算，所以数组索引从 0 开始。

补充：获取数组长度

public class ArrayLengthExample {
       public static void main(String[] args) {
           int[] array = {1, 2, 3, 4, 5};
           int length = array.length;
           System.out.println("数组的长度为: " + length);
       }
   }

数组获取索引值

   public class ArrayIndexAccess {
       public static void main(String[] args) {
           int[] array = {10, 20, 30, 40};
           int index = 2;
           int element = array[index];
           System.out.println("索引 " + index + " 处的元素是: " + element);
       }
   }

数组 - 插入和删除

数组插入

往数组里面插入一个元素的速度，取决于你需要把它插入到哪个位置上。

假设为周末的事情做规划，暂定规划如下

eat breakfast  // 吃早饭
shopping       // 购物
have lunch     // 吃午饭
have dinner    // 吃晚饭

如果把安排设置一个类，预留明天 20 个任务，那么代码如下：

public class Schedule {

  String[] array = new String[20];
  private int size = 0;

  // 内置4个安排
  public Schedule(){
    array[0] = "eat breakfast";
    array[1] = "shopping";
    array[2] = "have lunch";
    array[3] = "have dinner";
    this.size = 4;
  }

  public void print(){
    for(int i = 0; i < this.size; i++){
      System.out.print(this.array[i] + " ");
    }
  }

  public static void main(String[] args) {
    Schedule schedule = new Schedule();
    schedule.print();
  }
}

代码中内置了明天 4 个安排任务，并且设置任务数量size为 4。

尾部插入

如果现在突然想在吃完饭之后去看场电影（watch movie）：

public class Schedule {

  String[] array = new String[20];
  private int size = 0;

  // 内置4个安排
  public Schedule(){
    array[0] = "eat breakfast";
    array[1] = "shopping";
    array[2] = "have lunch";
    array[3] = "have dinner";
    this.size = 4;
  }

  public void add(String task){
    this.array[this.size] = task;
    this.size++;
  }

  public void print(){
    for(int i = 0; i < this.size; i++){
      System.out.print(this.array[i] + " ");
    }
  }

  public static void main(String[] args) {
    Schedule schedule = new Schedule();
    schedule.add("watch movie");
    schedule.print();
  }
}

在尾部插入元素很容易计算，尾部插入元素内存地址为

start_address + item_size * n  // n 为当前数组的个数

中间插入

如果希望在下午吃了午饭后喝一个下午茶（afternoon tea），那应该怎么处理呢？

我们知道，需要在数组中间部分插入数据，但是为了保证数组的顺序和连续的内存空间，插入地方后面部分数据，需要往后依次移动，如图所示：

一共需要几步呢？

1. 移动watch movie
2. 移动have dinner
3. 插入afternoon tea

如果插入在开始地方，则需要 N 步。

因此平均步数为 (1 + 2 + 3 + ... + N) / N 最终时间复杂度为O(N)，也就是数组的插入时间复杂度为线性时间复杂度。

可以新增一个insert3Position在索引位置为 3 的地方，插入一项任务：

// 第三个位置插入
public void insert3Position(String task) {
  // 索引值为3的地方
  int index = 3;
  // 第一步：从右侧开始依次右移
  for (int i = this.size - 1; i >= index; i--) {
    this.array[i + 1] = this.array[i];
  }
  // 第二步：插入元素
  this.array[index] = task;
  // 调整size
  this.size++;
}

空间不够

上面我们讨论都是正常情况，如果空间不够了呢？我们再次回顾下电影院的例子：

当我们有 4 个朋友的时候，当前位置是满足要求的。如果突然多来了一个朋友，位置不够了，这个时候需要重新找寻满足 5 个人位置的空间。

这和数组空间不够的原理是一样的，需要通过 3 步完成：

如上图所示，我们一起移动到下一排：

1. 开辟新的内存空间
2. 复制原来的数组到新的内存空间
3. 再进行插入操作

如果所有的内存空间都不足以存储到数组，这个时候系统就会抛出异常 --- Out Of Memory 内存不够。

举例：

public class YKDArrayList {

  // 此处需要声明一个数组，作为底层存储
  int[] array = new int[20];
  int size = 0;

  public YKDArrayList() {
  }

  // 获取数组的长度
  public int size() {
    return this.size;
  }

  // 数组获取某个索引值
  public int get(int index) {
    return this.array[index];
  }

  // 添加元素在末尾 
  public void add(int element) {
    //相当于调用传入this.size
    this.add(this.size, element);
  }

  // 添加元素在中间
  public void add(int index, int element) {
    if (index < 0 || index > this.size) {
      return;
    }

    // 支持扩容
    this.judgeMemory(this.size + 1);
    // 元素依次右移
    for (int i = this.size - 1; i >= index; i--) {
      this.array[i + 1] = this.array[i];
    }
    // 插入元素
    this.array[index] = element;
    // 调整size
    this.size++;
  }

  // 删除元素
  public void remove(int index) {
    if (index < 0 || index > this.size - 1) {
      return;
    }

    // 元素依次左移
    for (int i = index; i < this.size - 1; i++) {
      this.array[i] = this.array[i + 1];
    }
    // 删除最后一个元素
    this.array[this.size - 1] = 0;
    // 调整size
    this.size--;
  }

  private void judgeMemory(int size) {
    // 如果内存不满足，则需要扩容
    if (size > this.array.length) {
      // 申明两倍空间
      int[] newArray = new int[this.array.length * 2];
      // 拷贝操作
      this.copy(this.array, newArray);
      // 新数组赋值给原数组
      this.array = newArray;
    }
  }

  // 拷贝操作
  private void copy(int[] source, int[] aim) {
    for (int i = 0; i < source.length; i++) {
      aim[i] = source[i];
    }
  }

  public static void main(String[] args) {
    YKDArrayList ykdArrayList = new YKDArrayList();
    ykdArrayList.add(1);
    ykdArrayList.add(2);
    ykdArrayList.add(3);
    ykdArrayList.add(4);

    ykdArrayList.add(0, 5);

    ykdArrayList.remove(3);
  }
}

数组删除

数组的删除操作和插入操作刚好相反。

如果是删除尾部元素，则直接删除；

如果是删除中间元素通过两步执行：

1. 删除中间元素
2. 元素右侧其他元素依次左移

因此我们可以得知数组删除的时间复杂度也为O(N)。

总结

数组优势：数组的查询数据特别快，时间复杂度是 O(1)

数组劣势：数组的插入和删除比较慢，时间复杂度是 O(N) 数组需要连续内存空间，并且会申请额外的内存空间便于其扩展，这种数据结构对内存要求比较高，利用率低。

因为这些优势和劣势，我们在高频查询，低频插入和删除的情况下，可以选择数组作为底层数据结构。同时我们知道 Java 中的ArrayList，实际上在底层就是利用数组实现的。