2.3 数据结构

数据结构一直是技术面试的重点，大多数面试题都是围绕着数组、字符串、链表、树、栈及队列这几种常见的数据结构展开的，因此每一个应聘者都要熟练掌握这几种数据结构。

数组和字符串是两种最基本的数据结构，它们用连续内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构。由于操作链表和树需要操作大量的指针，应聘者在解决相关问题的时候一定要留意代码的鲁棒性，否则容易出现程序崩溃的问题。栈是一个与递归紧密相关的数据结构，同样队列也与广度优先遍历算法紧密相关，深刻理解这两种数据结构能帮助我们解决很多算法问题。

2.3.1 数组

数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。

由于数组中的内存是连续的，于是可以根据下标在O(1)时间读/写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值（Key），而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个“键值-值”的配对。有了这样的哈希表，我们就可以在O(1)时间内实现查找，从而快速、高效地解决很多问题。面试题50“第一个只出现一次的字符”就是一个很好的例子。

为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，比如C++的STL中的vector。为了避免浪费，我们先为数组开辟较小的空间，然后往数组中添加数据。当数据的数目超过数组的容量时，我们再重新分配一块更大的空间（STL的vector每次扩充容量时，新的容量都是前一次的两倍），把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。但我们也注意到每一次扩充数组容量时都有大量的额外操作，这对时间性能有负面影响，因此使用动态数组时要尽量减少改变数组容量大小的次数。

在C/C++中，数组和指针是既相互关联又有区别的两个概念。当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。我们可以用一个指针来访问数组。但值得注意的是，C/C++没有记录数组的大小，因此在用指针访问数组中的元素时，程序员要确保没有超出数组的边界。下面通过一个例子来了解数组和指针的区别。运行下面的代码，请问输出是什么？

int GetSize(int data[])

{

return sizeof(data);

}

int _tmain(int argc, _TCHAR* 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字节，因此共占用20字节。data2声明为指针，尽管它指向了数组data1的第一个数字，但它的本质仍然是一个指针。在32位系统上，对任意指针求sizeof，得到的结果都是4。在C/C++中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。因此，尽管函数GetSize的参数data被声明为数组，但它会退化为指针，size3的结果仍然是4。

面试题3：数组中重复的数字

题目一：找出数组中重复的数字。

在一个长度为n的数组里的所有数字都在0～n1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。

解决这个问题的一个简单的方法是先把输入的数组排序。从排序的数组中找出重复的数字是一件很容易的事情，只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要O(nlogn)的时间。

还可以利用哈希表来解决这个问题。从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字，就把它加入哈希表。如果哈希表里已经存在该数字，就找到一个重复的数字。这个算法的时间复杂度是O(n)，但它提高时间效率是以一个大小为O(n)的哈希表为代价的。我们再看看有没有空间复杂度是O(1)的算法。

我们注意到数组中的数字都在0～n1的范围内。如果这个数组中没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

现在让我们重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了）；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。

以数组{2, 3, 1, 0, 2, 5, 3}为例来分析找到重复数字的步骤。数组的第0个数字（从0开始计数，和数组的下标保持一致）是2，与它的下标不相等，于是把它和下标为2的数字1交换。交换之后的数组是{1, 3, 2, 0, 2, 5, 3}。此时第0个数字是1，仍然与它的下标不相等，继续把它和下标为1的数字3交换，得到数组{3, 1, 2, 0, 2, 5, 3}。接下来继续交换第0个数字3和第3个数字0，得到数组{0, 1, 2, 3, 2, 5, 3}。此时第0个数字的数值为0，接着扫描下一个数字。在接下来的几个数字中，下标为1、2、3的3个数字分别为1、2、3，它们的下标和数值都分别相等，因此不需要执行任何操作。接下来扫描到下标为4的数字2。由于它的数值与它的下标不相等，再比较它和下标为2的数字。注意到此时数组中下标为2的数字也是2，也就是数字2在下标为2和下标为4的两个位置都出现了，因此找到一个重复的数字。

上述思路可以用如下代码实现：

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;

}

// swap numbers[i] and numbers[numbers[i]]

int temp = numbers[i];

numbers[i] = numbers[temp];

numbers[temp] = temp;

}

}

return false;

}

在上述代码中，找到的重复数字通过参数duplication传给函数的调用者，而函数的返回值表示数组中是否有重复的数字。当输入的数组中存在重复的数字时，返回true；否则返回false。

代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。另外，所有的操作步骤都是在输入数组上进行的，不需要额外分配内存，因此空间复杂度为O(1)。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/03_01_DuplicationInArray

测试用例：

长度为n的数组里包含一个或多个重复的数字。

数组中不包含重复的数字。

无效输入测试用例（输入空指针；长度为n的数组中包含0～n1之外的数字）。

本题考点：

考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。

考查应聘者分析问题的能力。当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，是能否解决这个问题的关键所在。

题目二：不修改数组找出重复的数字。

在一个长度为n+1的数组里的所有数字都在1～n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

这一题看起来和上面的面试题类似。由于题目要求不能修改输入的数组，我们可以创建一个长度为n+1的辅助数组，然后逐一把原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组中下标为m的位置。这样很容易就能发现哪个数字是重复的。由于需要创建一个数组，该方案需要O(n)的辅助空间。

接下来我们尝试避免使用O(n)的辅助空间。为什么数组中会有重复的数字？假如没有重复的数字，那么在从1～n的范围里只有n个数字。由于数组里包含超过n个数字，所以一定包含了重复的数字。看起来在某范围里数字的个数对解决这个问题很重要。

我们把从1～n的数字从中间的数字m分为两部分，前面一半为1～m，后面一半为m+1～n。如果1～m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1～n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。

我们以长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}为例分析查找的过程。根据题目要求，这个长度为8的所有数字都在1～7的范围内。中间的数字4把1～7的范围分为两段，一段是1～4，另一段是5～7。接下来我们统计1～4这4个数字在数组中出现的次数，它们一共出现了5次，因此这4个数字中一定有重复的数字。

接下来我们再把1～4的范围一分为二，一段是1、2两个数字，另一段是3、4两个数字。数字1或者2在数组中一共出现了两次。我们再统计数字3或者4在数组中出现的次数，它们一共出现了三次。这意味着3、4两个数字中一定有一个重复了。我们再分别统计这两个数字在数组中出现的次数。接着我们发现数字3出现了两次，是一个重复的数字。

上述思路可以用如下代码实现：

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)。和最前面提到的需要O(n)的辅助空间的算法相比，这种算法相当于以时间换空间。

需要指出的是，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组{2, 3, 5, 4, 3, 2, 6, 7}中重复的数字2。这是因为在1～2的范围里有1和2两个数字，这个范围的数字也出现2次，此时我们用该算法不能确定是每个数字各出现一次还是某个数字出现了两次。

从上述分析中我们可以看出，如果面试官提出不同的功能要求（找出任意一个重复的数字、找出所有重复的数字）或者性能要求（时间效率优先、空间效率优先），那么我们最终选取的算法也将不同。这也说明在面试中和面试官交流的重要性，我们一定要在动手写代码之前弄清楚面试官的需求。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/03_02_DuplicationInArrayNoEdit

测试用例：

长度为n的数组里包含一个或多个重复的数字。

数组中不包含重复的数字。

无效输入测试用例（输入空指针）。

本题考点：

考查应聘者对一维数组的理解及编程能力。一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素。

考查应聘者对二分查找算法的理解，并能快速、正确地实现二分查找算法的代码。

考查应聘者的沟通能力。应聘者只有具备良好的沟通能力，才能充分了解面试官的需求，从而有针对性地选择算法解决问题。

面试题4：二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

在分析这个问题的时候，很多应聘者都会把二维数组画成矩形，然后从数组中选取一个数字，分3种情况来分析查找的过程。当数组中选取的数字刚好和要查找的数字相等时，就结束查找过程。如果选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前选取位置的右边或者下边，如图2.1（a）所示。同样，如果选取的数字大于要查找的数字，那么要查找的数字应该在当前选取位置的上边或者左边，如图2.1（b）所示。

图2.1 二维数组中的查找

注：在数组中间选择一个数（深色方格），根据它的大小判断要查找的数字可能出现的区域（阴影部分）。

在上面的分析中，由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠，这问题看起来就复杂了，于是很多人就卡在这里束手无策了。

当我们需要解决一个复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。针对这个问题，我们不妨也从一个具体的例子入手。下面我们以在题目中给出的数组中查找数字7为例来一步步分析查找的过程。

前面我们之所以遇到难题，是因为我们在二维数组的中间选取一个数字来和要查找的数字进行比较，这就导致下一次要查找的是两个相互重叠的区域。如果我们从数组的一个角上选取数字来和要查找的数字进行比较，那么情况会不会变简单呢？

首先我们选取数组右上角的数字9。由于9大于7，并且9还是第4列的第一个（也是最小的）数字，因此7不可能出现在数字9所在的列。于是我们把这一列从需要考虑的区域内剔除，之后只需要分析剩下的3列，如图2.2（a）所示。在剩下的矩阵中，位于右上角的数字是8。同样8大于7，因此8所在的列我们也可以剔除。接下来我们只要分析剩下的两列即可，如图2.2（b）所示。

在由剩余的两列组成的数组中，数字2位于数组的右上角。2小于7，那么要查找的7可能在2的右边，也可能在2的下边。在前面的步骤中，我们已经发现2右边的列都已经被剔除了，也就是说7不可能出现在2的右边，因此7只有可能出现在2的下边。于是我们把数字2所在的行也剔除，只分析剩下的三行两列数字，如图2.2（c）所示。在剩下的数字中，数字4位于右上角，和前面一样，我们把数字4所在的行也删除，最后剩下两行两列数字，如图2.2（d）所示。

在剩下的两行两列4个数字中，位于右上角的刚好就是我们要查找的数字7，于是查找过程就可以结束了。

图2.2 在二维数组中查找7的步骤

注：矩阵中加阴影的区域是下一步查找的范围。

总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

把整个查找过程分析清楚之后，我们再写代码就不是一件很难的事情了。下面是上述思路对应的参考代码：

bool Find(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;

}

在前面的分析中，我们每次都选取数组查找范围内的右上角数字。同样，我们也可以选取左下角的数字。感兴趣的读者不妨自己分析一下每次都选取左下角数字的查找过程。但我们不能选择左上角数字或者右下角数字。以左上角数字为例，最初数字1位于初始数组的左上角，由于1小于7，那么7应该位于1的右边或者下边。此时我们既不能从查找范围内剔除1所在的行，也不能剔除1所在的列，这样我们就无法缩小查找的范围。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/04_ FindInPartiallySortedMatrix

测试用例：

二维数组中包含查找的数字（查找的数字是数组中的最大值和最小值；查找的数字介于数组中的最大值和最小值之间）。

二维数组中没有查找的数字（查找的数字大于数组中的最大值；查找的数字小于数组中的最小值；查找的数字在数组的最大值和最小值之间但数组中没有这个数字）。

特殊输入测试（输入空指针）。

本题考点：

考查应聘者对二维数组的理解及编程能力。二维数组在内存中占据连续的空间。在内存中从上到下存储各行元素，在同一行中按照从左到右的顺序存储。因此我们可以根据行号和列号计算出相对于数组首地址的偏移量，从而找到对应的元素。

考查应聘者分析问题的能力。当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，是能否解决这个问题的关键所在。这个题目只要从一个具体的二维数组的右上角开始分析，就能找到查找的规律，从而找到解决问题的突破口。

2.3.2 字符串

字符串是由若干字符组成的序列。由于字符串在编程时使用的频率非常高，为了优化，很多语言都对字符串做了特殊的规定。下面分别讨论C/C++和C#中字符串的特性。

C/C++中每个字符串都以字符'\0'作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串中都有一个额外字符的开销，稍不留神就会造成字符串的越界。比如下面的代码：

char str[10];

strcpy(str, "0123456789");

我们先声明一个长度为10的字符数组，然后把字符串"0123456789"复制到数组中。"0123456789"这个字符串看起来只有10个字符，但实际上它的末尾还有一个'\0'字符，因此它的实际长度为11字节。要正确地复制该字符串，至少需要一个长度为11字节的数组。

为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向相同的内存地址。但用常量内存初始化数组，情况却有所不同。下面通过一个面试题来学习这一知识点。运行下面的代码，得到的结果是什么？

int _tmain(int argc, _TCHAR* argv[])

{

char str1[] = "hello world";

char str2[] = "hello world";

char* str3 = "hello world";

char* str4 = "hello world";

if(str1 == str2)

printf("str1 and str2 are same.\n");

else

printf("str1 and str2 are not same.\n");

if(str3 == str4)

printf("str3 and str4 are same.\n");

else

printf("str3 and str4 are not same.\n");

return 0;

}

str1和str2是两个字符串数组，我们会为它们分配两个长度为12字节的空间，并把"hello world"的内容分别复制到数组中去。这是两个初始地址不同的数组，因此str1和str2的值也不相同，所以输出的第一行是"str1 and str2 are not same"。

str3和str4是两个指针，我们无须为它们分配内存以存储字符串的内容，而只需要把它们指向"hello world"在内存中的地址就可以了。由于"hello world"是常量字符串，它在内存中只有一个拷贝，因此str3和str4指向的是同一个地址。所以比较str3和str4的值得到的结果是相同的，输出的第二行是"str3 and str4 are same"。

在C#中，封装字符串的类型System.String有一个非常特殊的性质：String的内容是不能改变的。一旦试图改变String的内容，就会产生一个新的实例。请看下面的C#代码：

String str = "hello";

str.ToUpper();

str.Insert(0, " WORLD");

虽然我们对str执行了ToUpper和Insert两个操作，但操作的结果都是生成一个新的String实例并在返回值中返回，str本身的内容都不会发生改变，因此最终str的值仍然是"hello"。由此可见，如果试图改变String的内容，则改变之后的值只能通过返回值得到。用String进行连续多次修改，每一次修改都会产生一个临时对象，这样开销太大会影响效率。为此，C#定义了一个新的与字符串相关的类型StringBuilder，它能容纳修改后的结果。因此，如果要连续多次修改字符串内容，用StringBuilder是更好的选择。

和修改String的内容类似，如果我们试图把一个常量字符串赋值给一个String实例，那么也不是把String的内容改成赋值的字符串，而是生成一个新的String实例。请看下面的代码：

class Program

{

internal static void ValueOrReference(Type type)

{

String result = "The type " + type.Name;

if (type.IsValueType)

Console.WriteLine(result + " is a value type.");

else

Console.WriteLine(result + " is a reference type.");

}

internal static void ModifyString(String text)

{

text = "world";

}

static void Main(string[] args)

{

String text = "hello";

ValueOrReference(text.GetType());

ModifyString(text);

Console.WriteLine(text);

}

}

在上面的代码中，我们先判断String是值类型还是引用类型。类型String的定义是public sealed class String {...}。既然是class，那么String自然就是引用类型。接下来在方法ModifyString里，对text赋值一个新的字符串。我们要记得text的内容是不能被修改的。此时会先生成一个新的内容是"world"的String实例，然后把text指向这个新的实例。由于参数text没有加ref或者out，出了方法ModifyString之后，text还是指向原来的字符