关于面试:剑指offer-阅读笔记三数据结构之数组

8次阅读

共计 3241 个字符，预计需要花费 9 分钟才能阅读完成。

排版如果影响浏览能够 浏览原文

数组能够说是最简略的一种数据结构，它占据一块间断的内存并依照顺序存储数据。

创立数组时，须要先指定数组容器的大小，而后依据大小分配内存。

因为数组的内存是间断的，于是能够依据下标在 O(1)工夫读写任何元素，因而它的工夫效率很高。

依据数组工夫效率高的长处, 实现简略的哈希表 ，用数组来实现简略的哈希表，把数组的下标设为哈希表的键，数组元素为哈希表的值，
有了这样的哈希表，咱们能够在 O(1)工夫内查找。

为了解决数组空间效率不高的问题 ，人们又设计实现了多种动静数组，比方 c ++ 中的 STL 中的 vector，为了避免浪费，先为数组开拓较小的空间，而后往数组中增加数组。
当数组的数据超过数组容量时，咱们再重新分配一块更大的空间 (c++ 中 vector 为之前的两倍，python list 也为之前的两倍)，把之前的数据复制到新数组中，再把之前的内存开释。
这对工夫性能有负面影响，因而应用动静数组时要尽量减少扭转数组容量大小的次数。

在 c /c++ 中，数组和指针是既相干又有区别的概念，当咱们申明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。咱们能够用指针来拜访数组。
c/c++ 没有记录数组的大小，因而在拜访数组元素时，程序员要确保没有超出数组的边界。

运行上面代码，请问输入什么？

#include <iostream>
using namespace std;

int GetSize(int data[])
{return sizeof(data);
}

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

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

int size3 = GetSize(data1);
cout << size1 << endl << size2 << endl << size3 << endl;
return 0;
}

答案是：20，8，8，data 是一个数组，sizeof(data)求的是数组的大小，5 个整数，每个整数占 4 个字节，因而占 20 个字节。
data2 是指针，指针在 32 位操作系统上占 4 位，64 位操作系统占 8 位。在 c /c++ 中，当数组当作函数的参数进行传递时，数组就主动进化为同类型的指针。因而，只管函数 GetSize 的参数 data 被申明为数组，但他会进化为指针。

在一个长度为 n 的数组里的所有数字都在 0~n- 1 的范畴内。数组中某些数字是反复的，然而不晓得有几个数字是反复的了，也不晓得数字反复了几次。请找出数组中任意一个反复的数字。例如，如果输出长度为 7 的数组{2,3,1,0,2,5,3}, 那么对应的输入反复的数字 2 或者 3。

解法一: 解决这个问题的一个简略的方法是先把输出的数组排序。从排序的数组中找出反复的数字只须要扫描排序的数组就能够了。排序一个长度为 n 的数组须要 O(nlgn)的工夫。

解法二: 还能够利用哈希表来解决这个问题，从头到尾按程序扫描数组的每个数字，每扫描到一个数字的时候，都能够用 O(1)的工夫来判断哈希表里是否曾经蕴含了该数字，如果哈希表里还没有这个数字，就把它退出到哈希表。如果哈希表里曾经存在这个数字，就找到了一个反复的数字。这个算法的工夫复杂度是 O(n)，但它进步工夫效率是以一个大小为 O(n)的哈希表为代价的。

解法三: 咱们留神到数组中的数字都在 0~n- 1 的范畴内。如果这个数组中没有反复的数字，那么当数组排序之后数组 i 将呈现在下标为 i 的地位。因为数组中有反复的数字，有些地位可能存在多个数字。当初让咱们重排数组，从头到尾扫描数组，当扫描到下标 i 时，判断数组下标 i 的元素是否和 i 雷同（arr[i] == i），不雷同，则把它和第 arr[i]个数进行替换（swap(arr[i], arr[arr[i]])），直到 arr[i]和 i 等同，把 arr[i]放回属于他的地位。反复上述的操作。
直到咱们发现一个反复的数字。

arr[] = {2, 3, 1, 0, 2, 5, 3}
i = 0; arr[i] != i; swap(arr[i], arr[arr[i]]);  // {1, 3, 2, 0, 2, 5, 3}
   arr[i] != i; swap(arr[i], arr[arr[i]]);  // {3, 1, 2, 0, 2, 5, 3}
   arr[i] != i; swap(arr[i], arr[arr[i]]);  // {0, 1, 2, 3, 2, 5, 3}
i = 1; arr[i] == i;
i = 2; arr[i] == i;
i = 3; arr[i] == i;
i = 4; arr[i] != i; arr[arr[i]] = arr[i]; return arr[i];

c++: array_repeat.cpp

python: array_repeat.py

本题考点：

老查应聘者对一维数组的了解及编程能力。一维数组在内存种占据间断的空间，因而咱们能够依据下标定位对应的元素。
考查应聘者剖析问题的能力。当应聘者发现问题比较复杂时。能不能通过具体的例子找出其中的法则，是是否解决这个问题的要害。

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

解法一: 看起来和上一题相似，因为题目要求不能批改输出的数组，咱们能够创立一个 n + 1 的数组为哈希表来辅助，则须要 O(n)的空间，O(n)的工夫。

解法二: 接下来咱们尝试 O(1)的空间，咱们把从 1 - n 是数字从两头的数字 m 分为两局部，前一半为 1m，后一半为 m +1n，如果 1~m 的数字呈现的次数超过 m，那么这一半必定有反复的数字，否则另一半必定有反复的数字。咱们能够持续把反复的区间一分为二，直到找到一个反复的数字。这个过程和二分法很像，只是多了一步统计区间里的数字。
每次统计范畴内的数字 O(n)，二分查找 O(lgn)，工夫复杂度为 O(nlgn)，空间复杂度为 O(1)，这是利用工夫换空间的算法。

int nums[] = {2, 3, 5, 4, 3, 2, 6, 7};  // length = 8;
//mid=(1+8)/2, 1~4 呈现了 5 次，5-7 呈现了 3 次，反复数字在 1~4 内
//mid=(1+4)/2, 1~2 呈现了 2 次，3-4 呈现了 3 次，反复数字在 3~4 内
//mid=(3+4)/2, 3 呈现了 2 次，4 呈现了 1 次，反复数字为 3

须要指出的是，这种算法并不能找出所有反复的数字。例如上例，咱们只找出了 3，其实 2 也是反复的，所以如果面试官要求的性能不同或是性能要求不同，咱们抉择的算法也不雷同，这就须要和面试官沟通。

c++: array_repeat2.cpp
python: array_repeat2.py

本题考查：

考查一维数组的了解和编程能力。
考查应聘者对二分法的了解，并能疾速、正确地实现二分查找算法。
考查应聘者的沟通能力，应聘者只有具备良好的沟通能力，能力充沛理解面试官的需要，从而针对性地抉择算法解决问题。

在一个二维数组中，每一行都依照从左到右的递增的程序排序，每一列都依照从上到下的程序排序。请实现一个函数，输出这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解法一: 遍历数组，判断指标元素是否在二维数组内，工夫复杂度 O(m*n), 空间复杂度 O(1);
解法二: 找到指标元素所在的列，遍历指标列，工夫复杂度 O(m+n)，空间复杂度 O(1);
解法三: 从最右上角开始找，首先，咱们选取数组右上角的 9，因为 9 >7, 并且 9 还是第 4 列的最小的数，因而 7 不可能呈现在数字 9 所在列，于是咱们把这一列从须要思考的区域踢出，整个过程如下如所示。

c++: find_number_in_2D_array.cpp
python: find_number_in_2D_array.py

正文完