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

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

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

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

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

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

关键点1

在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被申明为数组，但他会进化为指针。

面试题3:

找出数组中反复的数字

在一个长度为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

本题考查：

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

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

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

解法一: 遍历数组，判断指标元素是否在二维数组内，工夫复杂度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