数据结构与算法

一、数组

1. 概述

定义：在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识。

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

int[] array = {1,2,3,4,5}

知道了数组的数据起始地址BaseAddress，就可以由公式BaseAddress + i * size来计算索引i元素的地址

i即索引，在Java、C等语言都是从0开始
size是每个元素占用字节，了例如int占4，double占8

空间占用

Java中数组结构为

8字节markword，记录对象的锁状态、对象实例的哈希值、年龄信息、GC状态
4字节class指针（压缩class指针的情况）
4字节数组大小（决定了数组最大容量是2^32
数组元素 + 对齐字节（Java中所有对象大小都是8字节的整数倍，不足的要用对齐字节补足）

例如

int[] array = {1, 2, 3, 4, 5};

的大小为40字节，组成如下

8 + 4 + 4 + 5*4 + 4(alignment)

随机访问性能

即根据索引查找元素，时间复杂度是O(1)。

2. 动态数组

Java示例

public class DynamicArray implements Iterable<Integer> {private int size = 0; // 逻辑大小private int capacity = 8; // 容量private int[] array = {};/*** 向最后位置 [size] 添加元素** @param element 待添加元素*/public void addLast(int element) {add(size, element);}/*** 向 [0 .. size] 位置添加元素** @param index   索引位置* @param element 待添加元素*/public void add(int index, int element) {checkAndGrow();// 添加逻辑if (index >= 0 && index < size) {// 向后挪动, 空出待插入位置System.arraycopy(array, index,array, index + 1, size - index);}array[index] = element;size++;}private void checkAndGrow() {// 容量检查if (size == 0) {array = new int[capacity];} else if (size == capacity) {// 进行扩容, 1.5 1.618 2capacity += capacity >> 1;int[] newArray = new int[capacity];System.arraycopy(array, 0,newArray, 0, size);array = newArray;}}/*** 从 [0 .. size) 范围删除元素** @param index 索引位置* @return 被删除元素*/public int remove(int index) { // [0..size)int removed = array[index];if (index < size - 1) {// 向前挪动System.arraycopy(array, index + 1,array, index, size - index - 1);}size--;return removed;}/*** 查询元素** @param index 索引位置, 在 [0..size) 区间内* @return 该索引位置的元素*/public int get(int index) {return array[index];}/*** 遍历方法1** @param consumer 遍历要执行的操作, 入参: 每个元素*/public void foreach(Consumer<Integer> consumer) {for (int i = 0; i < size; i++) {// 提供 array[i]// 返回 voidconsumer.accept(array[i]);}}/*** 遍历方法2 - 迭代器遍历*/@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() { // 有没有下一个元素return i < size;}@Overridepublic Integer next() { // 返回当前元素,并移动到下一个元素return array[i++];}};}/*** 遍历方法3 - stream 遍历** @return stream 流*/public IntStream stream() {return IntStream.of(Arrays.copyOfRange(array, 0, size));}
}

这些方法实现，都简化了index的有效性判断，假设输入的index都是合法的。

插入或删除性能

头部位置，时间复杂度是O(n)
中间位置，时间复杂度是O(n)
尾部位置，时间复杂度是O(1)

3. 二维数组

int[][] array = {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};

内存图如下：

二维数组占32个字节，其中array[0]，array[1]，array[2]三个元素分别保存了指向三个一维数组的引用

三个一维数组各占40个字节
它们在内层布局上是连续的

更一般的，对一个二维数组Array[m][n]

m是外层数组的长度，可以看作row行
n是内层数组的长度，可以看作column列

当访问Array[i][j]时，就相当于

先找到第i个内层数组（行）
再找到此内存数组中第j个元素（列）

小测试

Java环境下（不考虑类指针和引用压缩，此为默认情况），有下面的二维数组

byte[][] array = {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};

已知array对象起始地址是0x1000，那么23这个元素的地址是什么？

答：

起始地址 0x1000
外层数组大小：16字节对象头 + 3元素 * 每个引用4字节 + 4 对齐字节 = 32 = 0x20
第一个内层数组大小：16字节对象头 + 5元素 * 每个byte1字节 + 3 对齐字节 = 24 = 0x18
第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2
最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

4. 局部性原理

这里只讨论空间局部性

cpu读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，存缓存中能读到的话，就不必读内存了
缓存的最小存储单位是缓存行（cache line），一般是64bytes，一次读的数据少了不划算，因此最少读64bytes填满一个缓存行，因此读入某个数据时，也会读取其临近的数据，这就是空间局部性。

对效率的影响

比较下面 ij 和 ji两个方法的执行效率

int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());

ij方法

public static void ij(int[][] a, int rows, int columns) {long sum = 0L;for (int i = 0; i < rows; i++) {for (int j = 0; j < columns; j++) {sum += a[i][j];}}System.out.println(sum);
}

ji方法

public static void ji(int[][] a, int rows, int columns) {long sum = 0L;for (int j = 0; j < columns; j++) {for (int i = 0; i < rows; i++) {sum += a[i][j];}}System.out.println(sum);
}

执行结果

0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
016196200  017%  ij
080087100  083%  ji

可以看到 ij 的效率比 ji快很多，为什么呢？

缓存是有限的，当新数据来了之后，一些旧的缓存行数据就会被覆盖
如果不能充分利用缓存的数据，就会造成效率低下

以 ji 执行为例，第一次内循环要读入[0, 0]这条数据，由于局部性原理，读入[0, 0]的同时也读入了[0, 0] ... [0, 13]，如图所示

但很遗憾，第二次内循环要的是[1, 0]这条数据，缓存中没有，于是再读入了下图的数据

这显然是一种浪费，因为[0, 1] ... [0, 13]，包括[1, 1] ... [1, 13]这些数据虽然读入了缓存，却没有及时用上，而缓存的大小是有限的，等执行到第九次内循环时

缓存的第一行数据已经被新的数据[8, 0] ... [8, 13]覆盖掉了，以后如果想再读，比如[0, 1]，又得到内存去读了。同理可以分析ij函数则能充分利用局部性原理加载到的缓存数据。

举一反三

1. I/O读写时同样可以体现局部性原理

2. 数组可以充分利用局部性原理，那么链表呢？

答：链表不行，因为链表的元素并非相邻存储

5. 越界检查

java中对数组元素的读写都有越界检查，类似于下面的代码

bool is_within_bounds(int index) const        
{ return 0 <= index && index < length(); 
}

此检查代码不需要由程序员来调用，JVM会帮我们调用

6. 习题

6.1 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

解法一：使用双指针法从后向前填充 nums1，避免了覆盖尚未比较的元素

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m + n - 1;m--;n--;while(n >= 0) {if(m >= 0 && nums1[m] > nums2[n]) {nums1[i--] = nums1[m--];} else {nums1[i--] = nums2[n--];}}}
}