剑指Offer中一共有12道关于数组的面试题
目录
面试题3：数组中重复的数字
面试题4：二维数组中的查找
面试题11：旋转数组的最小数字
面试题21：调整数组顺序使奇数位于偶数前面
面试题39：数组中出现次数超过一半的数字
面试题42：连续子数组的最大和
面试题45：把数组排成最小的数
面试题51：数组中的逆序对
面试题53：在排序数组中查找数字
面试题56：数组中数字出现的次数
面试题57：和为s的数字
面试题66：构建乘积数组
面试题3：数组中重复的数字
题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
详情见：【剑指Offer】面试题3：数组中重复的数字——JS实现
面试题4：二维数组中的查找
题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <cstdio> 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; }
面试题11：旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <cstdio> #include <exception> int MinInOrder(int* numbers, int index1, int index2); int Min(int* numbers, int length) { if(numbers == nullptr || length <= 0) throw new std::exception("Invalid parameters"); int index1 = 0; int index2 = length - 1; int indexMid = index1; while(numbers[index1] >= numbers[index2]) { // 如果index1和index2指向相邻的两个数， // 则index1指向第一个递增子数组的最后一个数字， // index2指向第二个子数组的第一个数字，也就是数组中的最小数字 if(index2 - index1 == 1) { indexMid = index2; break; } // 如果下标为index1、index2和indexMid指向的三个数字相等，比如：10111 // 则只能顺序查找 indexMid = (index1 + index2) / 2; if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1]) return MinInOrder(numbers, index1, index2); // 缩小查找范围 if(numbers[indexMid] >= numbers[index1]) index1 = indexMid; else if(numbers[indexMid] <= numbers[index2]) index2 = indexMid; } return numbers[indexMid]; } int MinInOrder(int* numbers, int index1, int index2) { int result = numbers[index1]; for(int i = index1 + 1; i <= index2; ++i) { if(result > numbers[i]) result = numbers[i]; } return result; }
面试题21：调整数组顺序使奇数位于偶数前面
题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：两个指针分别指向数组首尾，且分别移动到偶数和奇数时停止，并交换数值，直到第一个指针位于第二个指针后面停止。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#include <cstdio> void ReorderOddEven_1(int *pData, unsigned int length) { if(pData == nullptr || length == 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while(pBegin < pEnd) { // 向后移动pBegin，直到它指向偶数 while(pBegin < pEnd && (*pBegin & 0x1) != 0) pBegin ++; // 向前移动pEnd，直到它指向奇数 while(pBegin < pEnd && (*pEnd & 0x1) == 0) pEnd --; if(pBegin < pEnd) { int temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; } } }
面试题39：数组中出现次数超过一半的数字
题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法一:
思路：如果将数组排序，则该数字一定是统计学上的中位数，即长度为n的数组中第 n/2 大的数字。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#include <cstdio> #include "..UtilitiesArray.h" bool g_bInputInvalid = false; bool CheckInvalidArray(int* numbers, int length) { g_bInputInvalid = false; if(numbers == nullptr && length <= 0) g_bInputInvalid = true; return g_bInputInvalid; } bool CheckMoreThanHalf(int* numbers, int length, int number) { int times = 0; for(int i = 0; i < length; ++i) { if(numbers[i] == number) times++; } bool isMoreThanHalf = true; if(times * 2 <= length) { g_bInputInvalid = true; isMoreThanHalf = false; } return isMoreThanHalf; } int Partition(int data[], int length, int start, int end) { if(data == nullptr || length <= 0 || start < 0 || end >= length){ throw new std::exception("Invalid Parameters"); } int index = RandomInRange(start,end); // 生成一个随机数 Swap(&data[index], &data[end]); // 交换两个数字 int small = start-1; for(index = start; index < end; ++index){ if(data[index] < data[end]){ ++small; if(small != index){ Swap(&data[index], &data[small]); } } } ++small; Swap(&data[small], &data[end]); return small; } int MoreThanHalfNum_Solution1(int* numbers, int length) { if(CheckInvalidArray(numbers, length)) return 0; int middle = length >> 1; int start = 0; int end = length - 1; int index = Partition(numbers, length, start, end); while(index != middle) { if(index > middle) { end = index - 1; index = Partition(numbers, length, start, end); } else { start = index + 1; index = Partition(numbers, length, start, end); } } int result = numbers[middle]; if(!CheckMoreThanHalf(numbers, length, result)) result = 0; return result; }
解法二：
思路：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数多于其他数字出现次数的和。因此，我们可以在遍历数组时，保留两个值：一个是数组中的一个数字，另一个是次数。当我们遍历下一个数字时，如果和我们之前保留的数字相同，则次数加1，否则减1。如果次数为零，我们需要保留下一个数字，并将次数设为1。所以，最后把次数设为1的数字就是我们要找的数字。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int MoreThanHalfNum_Solution2(int* numbers, int length) { if(CheckInvalidArray(numbers, length)) return 0; int result = numbers[0]; int times = 1; for(int i = 1; i < length; ++i) { if(times == 0) { result = numbers[i]; times = 1; } else if(numbers[i] == result) times++; else times--; } if(!CheckMoreThanHalf(numbers, length, result)) result = 0; return result; }
面试题42：连续子数组的最大和
题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <cstdio> bool g_InvalidInput = false; int FindGreatestSumOfSubArray(int *pData, int nLength) { if((pData == nullptr) || (nLength <= 0)) { g_InvalidInput = true; return 0; } g_InvalidInput = false; int nCurSum = 0; int nGreatestSum = 0x80000000; for(int i = 0; i < nLength; ++i) { if(nCurSum <= 0) nCurSum = pData[i]; else nCurSum += pData[i]; if(nCurSum > nGreatestSum) nGreatestSum = nCurSum; } return nGreatestSum; }
面试题45：把数组排成最小的数
题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution { public: static bool cmp(int a,int b) { string A=""; string B=""; A+=to_string(a); A+=to_string(b); B+=to_string(b); B+=to_string(a); return A<B; } string PrintMinNumber(vector<int> numbers) { string answer=""; sort(numbers.begin(),numbers.end(),cmp); for(int i=0;i<numbers.size();i++) { answer+=to_string(numbers[i]); } return answer; } };
面试题51：数组中的逆序对
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如，在数组{7，5，6，4}中，一共存在5个逆序对，分别是（7，6）、（7，5）、（7，4）、（6，4）和（5，4）。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <cstdio> int InversePairsCore(int* data, int* copy, int start, int end); int InversePairs(int* data, int length) { if(data == nullptr || length < 0) return 0; int* copy = new int[length]; for(int i = 0; i < length; ++i) copy[i] = data[i]; int count = InversePairsCore(data, copy, 0, length - 1); delete[] copy; return count; } int InversePairsCore(int* data, int* copy, int start, int end) { if(start == end) { copy[start] = data[start]; return 0; } int length = (end - start) / 2; int left = InversePairsCore(copy, data, start, start + length); int right = InversePairsCore(copy, data, start + length + 1, end); // i初始化为前半段最后一个数字的下标 int i = start + length; // j初始化为后半段最后一个数字的下标 int j = end; int indexCopy = end; int count = 0; while(i >= start && j >= start + length + 1) { if(data[i] > data[j]) { copy[indexCopy--] = data[i--]; count += j - start - length; } else { copy[indexCopy--] = data[j--]; } } for(; i >= start; --i) copy[indexCopy--] = data[i]; for(; j >= start + length + 1; --j) copy[indexCopy--] = data[j]; return left + right + count; }
面试题53：在排序数组中查找数字
题目一：数字在排序数组中出现的次数
题目描述：统计一个数字在排序数组中出现的次数。
思路：利用二分查找找到第一个K和最后一个K的位置，时间复杂度为O(logn)。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#include <cstdio> int GetFirstK(const int* data, int length, int k, int start, int end); int GetLastK(const int* data, int length, int k, int start, int end); int GetNumberOfK(const int* data, int length, int k) { int number = 0; if(data != nullptr && length > 0) { int first = GetFirstK(data, length, k, 0, length - 1); int last = GetLastK(data, length, k, 0, length - 1); if(first > -1 && last > -1) number = last - first + 1; } return number; } // 找到数组中第一个k的下标。如果数组中不存在k，返回-1 int GetFirstK(const int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start + end) / 2; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0) return middleIndex; else end = middleIndex - 1; } else if(middleData > k) end = middleIndex - 1; else start = middleIndex + 1; return GetFirstK(data, length, k, start, end); } // 找到数组中最后一个k的下标。如果数组中不存在k，返回-1 int GetLastK(const int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start + end) / 2; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length - 1) return middleIndex; else start = middleIndex + 1; } else if(middleData < k) start = middleIndex + 1; else end = middleIndex - 1; return GetLastK(data, length, k, start, end); }
题目二：0~n-1中缺失的数字
题目描述：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
思路：题目可以转换在排序数组中找到第一个和下标不相等的元素——二分查找。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <cstdio> int GetMissingNumber(const int* numbers, int length) { if(numbers == nullptr || length <= 0) return -1; int left = 0; int right = length - 1; while(left <= right) { int middle = (right + left) >> 1; if(numbers[middle] != middle) { if(middle == 0 || numbers[middle - 1] == middle - 1) return middle; right = middle - 1; } else left = middle + 1; } if(left == length) return length; // 无效的输入，比如数组不是按要求排序的， // 或者有数字不在0到n-1范围之内 return -1; }
题目三：数组中数值和下标相等的元素
题目描述：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。
思路：二分查找。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#include <cstdio> int GetNumberSameAsIndex(const int* numbers, int length) { if(numbers == nullptr || length <= 0) return -1; int left = 0; int right = length - 1; while(left <= right) { int middle = left + ((right - left) >> 1); if(numbers[middle] == middle) return middle; if(numbers[middle] > middle) right = middle - 1; else left = middle + 1; } return -1; }
面试题56：数组中数字出现的次数
题目一：数组中只出现一次的两个数字
题目描述：一个整型数组里除两个数字之外，其他数字都出现了两次。请找出这两个数字。要求时间复杂度O(n)，空间复杂度O(1)。
思路：异或。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#include <cstdio> unsigned int FindFirstBitIs1(int num); bool IsBit1(int num, unsigned int indexBit); void FindNumsAppearOnce(int data[], int length, int* num1, int* num2) { if(data == nullptr || length < 2) return; int resultExclusiveOR = 0; for(int i = 0; i < length; ++i) resultExclusiveOR ^= data[i]; unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); *num1 = *num2 = 0; for(int j = 0; j < length; ++j) { if(IsBit1(data[j], indexOf1)) *num1 ^= data[j]; else *num2 ^= data[j]; } } // 找到num从右边数起第一个是1的位 unsigned int FindFirstBitIs1(int num) { int indexBit = 0; while(((num & 1) == 0) && (indexBit < 8 * sizeof(int))) { num = num >> 1; ++indexBit; } return indexBit; } // 判断数字num的第indexBit位是不是1 bool IsBit1(int num, unsigned int indexBit) { num = num >> indexBit; return (num & 1); }
题目二：数组中唯一只出现一次的数字
题目描述：在一个数组中除一个数字只出现一次以外，其他数字都出现了三次。请找出那个数字。
思路：我们把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除，那么那个只出现一次的数字二进制表示中对应的那一位是0；否则就是1。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <cstdio> #include <exception> int FindNumberAppearingOnce(int numbers[], int length) { if(numbers == nullptr || length <= 0) throw new std::exception("Invalid input."); int bitSum[32] = {0}; for(int i = 0; i < length; ++i) { int bitMask = 1; for(int j = 31; j >= 0; --j) { int bit = numbers[i] & bitMask; if(bit != 0) bitSum[j] += 1; bitMask = bitMask << 1; } } int result = 0; for(int i = 0; i < 32; ++i) { result = result << 1; result += bitSum[i] % 3; } return result; }
面试题57：和为s的数字
题目一：和为S的两个数字
题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <cstdio> bool FindNumbersWithSum(int data[], int length, int sum, int* num1, int* num2) { bool found = false; if(length < 1 || num1 == nullptr || num2 == nullptr) return found; int ahead = length - 1; int behind = 0; while(ahead > behind) { long long curSum = data[ahead] + data[behind]; if(curSum == sum) { *num1 = data[behind]; *num2 = data[ahead]; found = true; break; } else if(curSum > sum) ahead --; else behind ++; } return found; }
题目二：和为S的连续正数序列
题目描述：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <cstdio> void PrintContinuousSequence(int small, int big); void FindContinuousSequence(int sum) { if(sum < 3) return; int small = 1; int big = 2; int middle = (1 + sum) / 2; int curSum = small + big; while(small < middle) { if(curSum == sum) PrintContinuousSequence(small, big); while(curSum > sum && small < middle) { curSum -= small; small ++; if(curSum == sum) PrintContinuousSequence(small, big); } big ++; curSum += big; } } void PrintContinuousSequence(int small, int big) { for(int i = small; i <= big; ++ i) printf("%d ", i); printf("n"); }
面试题66：构建乘积数组
题目描述：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
思路：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <cstdio> #include <vector> using namespace std; void BuildProductionArray(const vector<double>& input, vector<double>& output) { int length1 = input.size(); int length2 = output.size(); if(length1 == length2 && length2 > 1) { output[0] = 1; for(int i = 1; i < length1; ++i) { output[i] = output[i - 1] * input[i - 1]; } double temp = 1; for(int i = length1 - 2; i >= 0; --i) { temp *= input[i + 1]; output[i] *= temp; } } }
END
最后
以上就是整齐大炮最近收集整理的关于【剑指Offer】面试题：数组的全部内容，更多相关【剑指Offer】面试题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[剑指offer] 数组中重复的数字](/uploads/reation/bcimg12.png)
发表评论 取消回复