|
关于数组的面试题总结(一)：
1. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | bool Find(int **matrix, int m, int n, int t) { bool found = false; if(matrix != NULL && m > 0 && n > 0) { int r = 0; int c = n - 1; while(r < m && c >= 0) { if(matrix[r][c] == t) {found = true; break;} else if(matrix[r][c] > t) --c; else ++r; } } return found; }
|
2. 采用递归的方法求数组所有元素的和
1
2
3
4
5 | // 采用递归的方法求数组元素之和 int sumArray(vector<int> &a, int n) { return 0 == n ? 0 : sumArray(a, n-1) + a[n-1]; }
|
3. 求数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。哎，这个题目居然WA了很多次，虽然看了剑指Offer，记得那个奇妙的计数方法，但是需要切记的是：找到可能的元素之后还需要再检查，因为给定的数组并不能保证一定有超过一半的数字出现。
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 | bool checkMoreThanHalf(vector<int> &arr, int target) { int times = 0; for(int i = 0; i < arr.size(); ++i) if(target == arr[i]) ++times; if(times * 2 <= arr.size()) return false; else return true; }
int moreThanHalf(vector<int> &arr) { if(0 == arr.size()) return -1; int num = arr[0]; int cnt = 1; for(int i = 1; i < arr.size(); ++i) { if(arr[i] == num) ++cnt; else if(cnt > 0) --cnt; else { num = arr[i]; cnt = 1; } } if(cnt > 0 && checkMoreThanHalf(arr, num)) return num; else return -1; }
|
来自CODE的代码片
NumberMoreThanHalf.cpp
4. 旋转数组（包括重复元素）的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | int minEleminArray(int arr[], int n) { if(0 == n) return -1; int l = 0, r = n - 1; while(l < r && arr[l] >= arr[r]) // note l < r { int m = l + ((r - l) >> 1); if(arr[m] == arr[r]) { int idx = r; while(m < idx && arr[m] == arr[idx]) --idx; if(m == idx) r = m; else l = m + 1; } else if(arr[m] > arr[r]) l = m + 1; else r = m; } return arr[l]; }
|
5. 在旋转数组（不包含重复元素）中查找指定元素，返回位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | // Search in Rotated Sorted Array (no duplicates) int search(int A[], int n, int target) { int l = 0, r = n - 1; while(l <= r) { int m = l + ((r - l) >> 1); if(A[m] == target) return m; else if(A[m] < A[r]) { if(target > A[m] && target <= A[r]) l = m + 1; else r = m - 1; } else { if(target >= A[l] && target < A[m]) r = m - 1; else l = m + 1; } } return -1; }
|
来自CODE的代码片
SearchRotatedArray.cpp
6. 在旋转数组（包含重复元素）中查找指定元素，返回是否存在
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 | // Search in Rotated Sorted Array II (duplicates) bool search2(int A[], int n, int target) { int l = 0, r = n - 1; while(l <= r) { int m = l + ((r - l) >> 1); if(A[m] == target) return true; else if(A[m] == A[r]){ int idx = r; while(m < idx && A[m] == A[idx]) --idx; if(A[m] == A[idx]) r = m - 1; else if(target >= A[l] && target < A[m]) r = m - 1; else l = m + 1; } else if(A[m] < A[r]) { if(target > A[m] && target <= A[r]) l = m + 1; else r = m - 1; } else { if(target >= A[l] && target < A[m]) r = m - 1; else l = m + 1; } } return false; }
|
来自CODE的代码片
SearchRotatedArray2.cpp
7. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。[九度]
下面是剑指Offer中介绍的方法，但是超时！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | void adjustArray(vector<int> &nums) { int odd = 0, p = 0; int n = nums.size(); while(p < n) { if(nums[p] & 0x1) { if(p == odd) { ++p; ++odd; } else { int tmpOdd = nums[p]; for(int i = p; i > odd; --i) nums[i] = nums[i-1]; nums[odd++] = tmpOdd; ++p; } } else ++p; } }
|
下面参考别人的方法AC了，但是不够漂亮！
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 | #include <cstdio> #include <iostream> #include <vector> using namespace std; int adjustArray(vector<int> &nums) { int odd = 0, p = 0; int n = nums.size(); while(p < n) { if(nums[p] & 0x1) { if(p < n-1 || odd > 0) printf("%d ", nums[p]); else printf("%d\n", nums[p]); ++p; } else nums[odd++] = nums[p++]; } return odd; } int main() { int n; vector<int> nums; scanf("%d", &n); nums.resize(n); for(int i = 0; i < n; ++i) scanf("%d", &nums[i]); int even = adjustArray(nums); for(int i = 0; i < even-1; ++i) printf("%d ", nums[i]); printf("%d", nums[even-1]); return 0; } /************************************************************** Problem: 1516 User: lanluo0909 Language: C++ Result: Accepted Time:70 ms Memory:1912 kb ****************************************************************/
|
8. 数组前半部分和后半部分分别有序（递增），采用O(1)的空间实现两部分的归并，这里暂不探究时间复杂度。
第一种方法，直观地对两段有序数组进行归并，left和right分别用来指向前半部分和后半部分我们正在考虑的元素，若left指向的小，则left直接后移即可，而若right指向的元素小，则需要互换left与right所指的之后，为了保证后半部分数组有序，需要将原left所指的值放在正确的位置。
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 | void combineSubArr(vector<int> &num) { if(1 >= num.size()) return; int left = 0, right = 1; while(num[right] >= num[right - 1]) ++right; int mid = right; while(left < mid) { if(num[left] > num[right]) { int tmp = num[left]; num[left] = num[right]; int j; for(j = right + 1; j < num.size(); ++j) { if(num[j] < tmp) num[j-1] = num[j]; else { num[j-1] = tmp; break; } } if(j >= num.size()) // note!! { num[j-1] = tmp; } } ++left; } }
|
第二种方法，有一点点技巧，因为上面的方法是将元素一个一个的调整到合适的位置，有时候可能后面部分有大片元素可以一起调整到合适的位置，如{7, 8, 9, 1, 2, 3,}，我们只需要经过一次变换将1,2,3集体移到恰当的位置，数组就有序了。
具体做法，设数组为O, A1, A2, ..., As, B1, B2, ..., Bt; （前面的O表示已有序的部分，初始情况为空）
我们还是需要left和right两个指针分别指向A和B部分的起始位置，当left指向的元素小时与上面一样，但当right所指向的元素小时，我们在B中沿着right向后找出所有比A1小的元素，不妨设B1 < B2 < B3 < ... < Bk < A1，接下来我们将B1...Bk这部分放到恰当的位置，就是把A1, A2, ..., As和 B1, B2, ..., Bk这两块交换，这是一个很典型的问题，可以通过三个反转操作实现。
原始数组： O, A1, A2, ..., As; B1, B2, ..., Bk, Bk+1, ..., Bt
A部分反转：O, As, As-1, ..., A1; B1, B2, ..., Bk, Bk+1, ..., Bt
B部分反转：O, As, As-1, ..., A1; Bk, Bk-1, ..., B1, Bk+1, ..., Bt
AB部分反转：O, B1, B2, ..., Bk; A1, A2, ..., As, Bk+1, ..., Bt
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 | void reverse(vector<int> &num, int l, int r) { while(l < r) { swap(num[l++], num[r--]); } }
void combineSubArr2(vector<int> &num) { if(1 >= num.size()) return; int left = 0, right = 1; while(num[right] >= num[right - 1]) ++right; int mid = right; while(left < mid) { if(num[left] > num[right]) { int j = right + 1; while(j < num.size() && num[j] < num[left]) ++j; if(j == right + 1) { swap(num[left], num[right]); } else { reverse(num, left, mid - 1); reverse(num, right, j - 1); reverse(num, left, j - 1); right = j; left += j - right; mid = right; // note!! } } else ++left; } }
|
9. 采用O(n)的时间和 O(1)的空间复杂度，实现通过数组a计算数组b，其中 bi = a1*a2*...*an/ai，不能使用除法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | void getMultiplcation(vector<int> &arr, vector<long long> &muls) { if(0 == arr.size()) return; muls[0] = 1; for(size_t i = 1; i < arr.size(); ++i) { muls[i] = muls[i-1] * arr[i-1]; } long long tmp = arr[arr.size() - 1]; for(int i = arr.size() - 2; i >= 0; --i) { muls[i] *= tmp; tmp *= arr[i]; } }
|
来自CODE的代码片
getMultiplcation.cpp
10. 求数组中子数组的连续最大乘积（最大连续子数组之和是很经典的动态规划，这里就不说了）
版本1：边界容易出错
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | long long maxSubarrMult(vector<int> &nums) { if(0 == nums.size()) return 0; long long preMin = nums[0]; long long preMax = nums[0]; long long ret = preMax; for(size_t i = 1; i < nums.size(); ++i) { if(preMax < 1) preMax = 1; //note: !!! if(preMin > -1) preMin = 1; // note: !!! preMin *= nums[i]; preMax *= nums[i]; if(preMin > preMax) swap(preMin, preMax); if(preMax > ret) ret = preMax; } return ret; }
|
版本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 | long long maxofThree(long long a, long long b, long long c) { return a > b ? (a > c ? a : c) : (b > c ? b : c); }
long long minofThree(long long a, long long b, long long c) { return a < b ? (a < c ? a : c) : (b < c ? b : c); }
long long maxSubarrMult2(vector<int> &nums) { if(0 == nums.size()) return 0; long long preMin = nums[0]; long long preMax = nums[0]; long long ret = preMax; for(size_t i = 1; i < nums.size(); ++i) { int tmpmax = preMax * nums[i]; int tmpmin = preMin * nums[i]; preMax = maxofThree(tmpmax, tmpmin, nums[i]);//不能把上述表达式直接放在这里，因为这样计算后preMax改变了 preMin = minofThree(tmpmax, tmpmin, nums[i]); if(preMax > ret) ret = preMax; } return ret; }
|
|
