《剑指 Offer》中数组的基础部分

数据结构

引言

数据结构一直是面试的重点，大多数会围绕着数组、字符串、链表、树、栈、队列等几种常见的数据结构展开，因此我们需要熟练掌握这几种数据结构。
数组和字符串是两种最为基础的数据结构，它们利用连续的内存存放数字和字符。而链表和树则是面试频率相对较高的数据结构。由于操作链表和树时需要操作相当数量的指针，因此在解决相关问题时，要特别重视相应的鲁棒性，否则容易出现程序崩溃的问题。栈与递归密切相关，而队列也和 BFS（广度优先遍历算法）密切相关，深刻理解这几种数据结构可以帮助我们解决很多问题。

鲁棒性：（英语：Robustness）也称稳健性、健壮性~~、耐操性~~。在计算机科学中，鲁棒性是指一个计算机系统在执行过程中处理错误，以及算法在遭遇输入、运算等异常时继续正常运行的能力。诸如模糊测试之类的形式化方法中，必须通过制造错误的或不可预期的输入来验证程序的鲁棒性。很多商业产品都可用来测试软件系统的鲁棒性。鲁棒性也是失效评定分析中的一个方面。~~（引用知乎答主@朱捷的回答）粗鲁的状态下也能表现的很棒~~

数组

基础概念

数组可以说是最简单的数据结构，它占据着一块连续的内存空间，按照顺序存储数据。创建数组时，我们需要指定容量的大小，然后根据大小分配内存。因此数组的空间利用率相对较低（很多时候定义的大小比实际利用的更大）。
由于数组空间连续，因此可以根据下标在$O(1)$的时间内读/写任何元素。从这个方面来看，它的时间效率很高。因此可以基于此来实现较为简单的哈希表：将下标设置为键值（Key），而每个数字设置为哈希表的值（Value），如此一来便可以在$O(1)$时间范围内实现查找，从而快速高效地解决很多的问题。
为了解决数组空间利用率不高的问题，人们设计实现了多种的动态数组，例如C++的STL中的vector。为了避免浪费，我们先开辟一个较小的空间，然后往里加数据。当数据数目超过容量时，我们重新分配一块较大的空间（STL的vector分配时会扩大一倍），把之前的内容复制到新数组中，再将之前的数组释放，这样可以减少内存的浪费。但同时注意到扩容会带来额外的时间开销，因此需要尽量减小改变容量大小的次数。
在C/C++中，数组和指针既有关联也互有区别。当声明数组时，其名字亦为一个指针，指针指向数组的第一个元素。我们可以利用一个指针来访问数组，但需要注意的是，C/C++没有记录数组的大小，因此利用指针访问元素时，需要确保访问不会越界。下面考虑这个例子：

// 在 32 位系统下运行
int getSize(int data[]) {
    return sizeof(data);
}

int main(int argc, char *argv[]) {
    int data1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(data1);

    int *data2 = data1;
    int size2 = sizeof(data2);

    int size3 = getSize(data1);

    printf("%d, %d, %d", size1, size2, size3);
}

那么执行这个程序的输出是多少呢？

查看答案与解析

答案是：20, 4, 4
data1是一个数组，sizeof(data1)可以求出数组的大小。这个数组包含了 5 个整数，每个整数占用 4 个字节（int类型），因此一共占用 20 个字节。data2声明为指针，尽管它指向了data1的第一个元素。对任意指针在 32 位系统下求sizeof，得到的结果都是 4。最后是data3，在C/C++中，数组传参时会退化为同类型的指针。因此data1作为参数传递后，仍会退化为指针。
下图为 Clion 给出的提示信息：
Clion 提示

题目分析

题目一

下面，我们看一道例题：

题目：找出数组中重复的数字
在一个长度为n的数组里的所有数字都在 0~n-1 的范围内，数组中的某些数字是重复的，但是不知道是几个数字重复，也不知道重复了多少次。请找出数组中任意一个重复的数字。
示例输入：[2, 3, 1, 0, 2, 5, 3]
示例输出：2（或 3）

解决的一个简单方案是先对数组进行排序，然后从头到尾进行扫描即可。而排序一个长度为n的数组需要$O(nlogn)$的时间。

排序法示例代码

int duplicate(int data[], int length) {
    // 当然也可以采用如下函数定义：
    // bool duplicate(int data[], int length, int* duplicate);
    // 相应的输出也需要更改，重复值可由 duplicate 指出

    // 使用 sort 函数时需要引入头文件 <algorithm>
    std::sort(data, data + length);
    for (int i = 0; i < length - 1; ++i) {
        if (data[i] == data[i + 1]) {
            return data[i];
        }
    }
    return -1;
}

我们还可以利用哈希表来解决这个问题。从头到尾顺序扫描每个数字，每扫描一个数字，我们可以用$O(1)$的时间判断其是否在表中，若无，则加入之，如果存在，则找到重复数字。它的时间复杂度为$O(n)$，但代价是空间复杂度也为$O(n)$（维护了一个大小为n的哈希表）

哈希表法示例代码

int duplicate(int data[], int length) {
    // 当然也可以采用如下函数定义：
    // bool duplicate(int data[], int length, int* duplicate);
    // 相应的输出也需要更改，重复值可由 duplicate 指出

    // 这里我们使用一个数组来维护哈希表
    bool hashMap[length];
    for (int i = 0; i < length; ++i) {
        hashMap[i] = false;
    }
    // 因长度为变量，故不能使用常规的初始化
    for (int i = 0; i < length; ++i) {
        if (!hashMap[data[i]]) {
            hashMap[data[i]] = true;
        } else {
            return data[i];
        }
    }
    return -1;
}

下面，我们考虑一个空间复杂度为$O(1)$的算法：
注意到数组的数字都在 0~n-1 的范围内，假设不存在重复的数字，那么排序后每个数字都将和其下标一致。如果存在重复的数字，有些位置就可能存在多个数字，对应的有些位置就没有。
下面我们重排数组：从头到尾依次扫描，当下标为 i 时，首先比较它（用 m 表示）是否与 i 相等，若是，扫描下一个；若不是，则与第 m 个数字比较，若相等，则出现重复；不等，则交换这两个数字，把 m 放到它应该待的地方，再次进行比较。重复这个过程，直到我们发现重复的数字。以下是取自书中的示例代码：

示例代码

bool duplicate(int numbers[], int length, int *duplication) {
    if (numbers == nullptr || length <= 0) {
        return false;
    }
    // 判断数组长度合法性，在我提供的示例代码中，忽略了这个问题，在实际操作时务必注意。
    for (int i = 0; i < length; ++i) {
        if (numbers[i] < 0 || numbers[i] > length - 1) {
            return false;
        }
    }
    // 判断元素的合法性

    for (int i = 0; i < length; ++i) {
        while (numbers[i] != i) {
            if (numbers[i] == numbers[numbers[i]]) {
                // 返回重复
                *duplication = numbers[i];
                return true;
            }

            // 常规的交换步骤
            int temp = numbers[i];
            numbers[i] = numbers[temp];
            numbers[temp] = temp;
        }
    }
    return false;
}

代码中尽管有两层循环，但每个数字最多交换两次即可回到它的位置，固总时间复杂度为$O(n)$。另外，所有的操作均在输入数组上进行，不需要额外分配内存，因此空间复杂度为$O(1)$。

题目二

下面我们考虑另一道题目：

题目：不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字重复。请找出任意一个重复的数字，但不能修改输入的数组。
示例输入：[2, 3, 5, 4, 3, 2, 6, 7]
示例输出：2（或 3）

这一题和上一题有些类似，但是增加了不能修改原有数组的条件，我们可以创建一个长度为n+1的辅助数组，然后逐个复制，对原数组 i 的元素，复制到新数组下标为 i 的位置。如此一来，我们便可以找出对应的重复元素。

辅助数组法示例代码

// 其实和第一题的哈希表法类似，我感觉直接拿来用都可以
int duplicate(int numbers[], int length) {
    int helper[length];
    for (int i = 0; i < length; i++) {
        helper[i] = -1;
    }
    for (int i = 0; i < length; i++) {
        if (-1 != helper[data[i]]) {
            helper[data[i]] = data[i];
        } else {
            return data[i];
        }
    }
    return -1;
}

接下来，我们避免使用$O(n)$的辅助空间。我们从这个方面考虑：为什么会有重复的数字？假如没有重复，那么在 1~n 范围内仅有 n 个数字。又数组长度为 n+1，根据抽屉原理（也称之为鸽笼原理），一定包含有重复的数字。

鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理。
其中一种简单的表述法为：
若有 n 个笼子和 n+1 只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少 2 只鸽子。
另一种为：
若有 n 个笼子和 kn+1 只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少 k+1 只鸽子。
集合论的表述如下：
若 A 是 n+1 元集，B 是 n 元集，则不存在从 A 到 B 的单射。

基于此，我们把从 1~n 的数字从中间数字 m 分为两部分，一半为 1~m，另一半为 m+1~n。如果 1~m 中数字数量超过 m，那么这区间内一定存在重复的数字；否则在零一区间内。基于此，我们继续把剩下的区间一分为二。这个过程同二分查找算法类似，仅仅多了一步统计区间内数字数目而已。
于是，我们有如下的实现方案：

示例代码

int getDuplication(const int *numbers, int length) {
    if (numbers == nullptr || length <= 0) {
        return -1;
    }
    int start = 1;
    int end = length - 1;
    while (end >= start) {
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers, length, start, middle);
        if (end == start) {
            if (count > 1) {
                return start;
            } else {
                break;
            }
        }
        if (count > (middle - start + 1)) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}

int countRange(const int *numbers, int length, int start, int end) {
    if (numbers == nullptr) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < length; i++) {
        if (numbers[i] >= start && numbers[i] <= end) {
            ++count;
        }
    }
    return count;
}

上述代码按照二分查找的思路，若输入长度为 n 的数组，那么函数countRange将被调用$O(logn)$次，每次需要$O(n)$的时间，故总时间复杂度为$O(nlogn)$，空间复杂度为$O(1)$。和上述辅助数组法相比，这属于空间换时间。
需要指出的是，这种算法不能保证找出所有的重复数字。

题目三

下面我们考虑二维数组的查找，请看例题：

题目：在一个二维数组中，每一行从左至右递增，每一列从上至下递增。请完成一个函数，输入二维数组和一个整数，判断数组中是否包含有该整数。
示例输入：
输入一：
[
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15]
]; 5
输入二：
数组不变，整数 7
示例输出：
输出一：true
输出二：false

题外话：二维数组的表示方式

对于二维数组，我们可以考虑两种方案：（示例代码给的是一维的二维映射方案）

1 2	int [row][col]; int [row * columns + col];

也即是考虑用一维数组表示二维数组的考虑。具体可以参照这个帖子。在此，我将参考结论给出：使用一维数组效率更高。下面这个图或许更为清晰：
一维数组与二维数组的比较

考虑问题

在分析问题时，大多数时间我们会画出二维数组的矩形，然后考虑选中的元素相对大小。分三种情况：

若选中的数字与查找数字相等，则结束查找
若选中的数字较小，那么目标可能在当前位置的右下（如图(a)）
若选中的数字较大，那么目标可能在当前位置的左上（如图(b)）

在上面的分析中，由于目标位置可能在两个区域（橙色）、并且还可能重叠（红色），因此会相对复杂一些，我们不妨考虑一下原因：
我们是从中间开始选择的，因此会产生这种交叉部分；但是，如果我们从边角开始，情况会不会好一些呢？如果我们从其中一个角（例如）开始，再逐行逐列筛选，情况应该会简单很多。

实例分析

为省略篇幅，留下四张图供读者自行分析。
我们在以下数组中寻找数字 7：

于是我们可以得出如下算法：

首先选取数组的右上角
判断该元素与目标的大小
若该元素与目标相等，结束查找
若该元素小于目标，则剔除该元素所在行
若该元素大于目标，则提出该元素所在列

如此一来，每一步都会减小查找的范围，直到命中或者范围为空。
基于此，我们有如下代码：

示例代码

在这里，我们使用一维数组代表矩阵，利用行列运算进行元素的定位。

bool find(const int *matrix, int rows, int columns, int number) {
    bool found = false;
    if (matrix != nullptr && rows > 0 && columns > 0) {
        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0) {
            if (matrix[row * columns + column] == number) {
                found = true;
                break;
            } else if (matrix[row * columns + column] > number) {
                --column;
            } else {
                ++row;
            }
        }
    }
    return found;
}

课后习题

在本例中，我们选择了右上角进行处理，那么其他三个角的状况如何呢？

西江月·证明
即得易见平凡，仿照上例显然。
留作习题答案略，读者自证不难。
反之亦然同理，推论自然成立，
略去过程QED，由上可知证毕。

（答案还是会给的，在下面）

参考答案

我们除了右上角之外还可以选择左下角，而左上角和右下角均不可。原因在于我们无法准确地区分应该朝着哪个方向前进（也即是剔除行/列无法判断）。