算法难，难如上青天，但是难也得静下心来慢慢学习，并总结归纳。所以将剑指 offer 中的题目按照类别进行了归纳，这是第一篇--数组篇。当然，如果各位大佬发现程序有什么 bug 或其他更巧妙的思路，欢迎交流学习。
3. 数组中重复的数字
题目一描述
在一个长度为 n 的数组里的所有数字都在 0~n-1 的范围内。数组中存在有重复的数字，但不知道有几个数字重复，也不知道重复了几次。请找出数组中任意一个重复的数字。
解题思路
由于数组中所有数字都在 0 ~ n-1 范围内，那么如果数组中没有重复的数字，则排序后的数组中，数字 i 就一定出现在下标为 i 的位置。
所以，可以在遍历数组的时候，判断：
- 如果当前位置元素
arr[i]等于i，则继续遍历； - 否则，将
arr[i]与arr[arr[i]]进行比较：- 如果相等，则表示找到了重复的数字；
- 否则，将它们两个进行交换，也就是将
arr[i]放到下标为i的位置。然后继续重复步骤2进行比较。
代码实现
public boolean duplicate(int[] arr, int[] duplication) { if (arr == null || arr.length <= 0) { return false; } for (int i = 0; i < arr.length; i++) { while (arr[i] != i) { if (arr[i] == arr[arr[i]]) { duplication[0] = arr[i]; return true; } int temp = arr[i]; arr[i] = arr[temp]; arr[temp] = temp; } } return false;}复制代码 这种方法，每一个数字最多只需要交换两次就可以归位：
- 第一次和当前正在遍历的元素进行交换；
- 第二次就可以将它归位。
因此时间复杂度是 O(n)。由于不需要额外空间，空间复杂度是 O(1)。
题目二描述
在一个长度为 n+1 的数组中所有数字都在 1~n 范围内，所以数组中至少有一个数字重复。请找出任意一个重复的数字，但是不能修改原有的数组。
解题思路
由于数组中所有数字都在 1 ~ n 范围内，所以可以将 1 ~ n 的数组从中间值 m 分为 1 ~ m 和 m+1 ~ n 两部分。如果 1 ~ m 之间的数字超过了 m 个，表示重复数字在 1 ~ m 之间，否则在 m+1 ~ n 之间。
然后继续将包含重复数字的区间分为两部分，继续判断直到找到一个重复的数字。
代码实现
public int duplicateNumber(int[] arr) { if (arr == null || arr.length <= 0) { return -1; } int start = 1; int end = arr.length - 1; while (start <= end) { int mid = ((end - start) >> 1) + start; int count = countRange(arr, start, mid); if (start == mid) { if (count > 1) { return start; } else { break; } } if (count > (mid - start + 1)) { end = mid; } else { start = mid + 1; } } return -1;}public int countRange(int[] arr, int start, int end) { int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] >= start && arr[i] <= end) { count++; } } return count;}复制代码 按照二分查找的思路，函数 countRange 会被调用 log(n) 次，每次需要 O(n) 的时间，所以总的时间复杂度是 O(nlogn)。
4. 二位数组中的查找
题目描述
在一个二维数组中，每一行按照从左到右递增的顺序排序，每一列按照从上到下递增的顺序排序。要求实现一个函数，输入一个二位数组和一个整数，判断该整数是否在数组中。
解题思路
这里可以选取左下角或右上角的元素进行比较。这里，以右上角为例：
对于右上角的元素，如果该元素大于要查找的数字，则要查找的数字一定在它的左边，将 col--，如果该元素小于要查找的数字，则要查找的数字一定在它的下边，将 row++，否则，找到了该元素，查找结束。
public boolean find(int target, int [][] array) { if(array == null || array.length <= 0 || array[0].length <= 0) { return false; } int row = 0; int col = array[0].length - 1; while(row < array.length && col >= 0){ if(array[row][col] > target) { col--; } else if(array[row][col] < target) { row++; } else { return true; } } return false;}复制代码 11. 旋转数组的最小数字
题目描述
将一个数组最开始的几个元素移动数组的末尾，称为旋转数组。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
解题思路
由于数组在一定程度上是有序的，所以可以采用类似二分查找的方法来解决。可以使用两个指针，start 指向数组的第一个元素，end 指向最后一个元素，接着让 mid 指向数组的中间元素。
这里需要考虑一类特殊情况，就是数组中存在重复元素，例如 1 1 1 0 1 或者 1 0 1 1 1 的情况，这时利用二分法已经不能解决，只能进行顺序遍历。
一般情况下，判断数组中间元素（mid）与数组最后一个元素（end）的大小，如果数组中间元素大于最后一个元素，则中间元素属于前半部分的非递减子数组，例如 3 4 5 1 2。此时最小的元素一定位于中间元素的后面，则将 start 变为 mid + 1。
否则的话，也就是数组中间元素（mid）小于等于最后一个元素（end），则中间元素属于后半部分的非递减子数组中，例如 2 0 1 1 1，或者 4 5 1 2 3。此时最小的元素可能就是中间元素，可能在中间元素的前面，所以将 end 变为 mid。
如此，直到 start 大于等于 end 退出循环时，start 指向的就是最小的元素。
代码实现
public int minNumberInRotateArray(int [] array) { if(array == null || array.length <= 0) { return 0; } int start = 0; int end = array.length - 1; // 数组长度为 1 时，该元素必然是最小的元素，也就不需要再判断 start == end 的情况 while(start < end) { int mid = start + ((end - start) >> 1); if (array[start] == array[end] && array[start] == array[mid]) { return min(array, start, end); } if(array[mid] > array[end]) { start = mid + 1; } else { end = mid; } } return array[start];}public int min(int[] array, int start, int end) { int min = array[start]; for(int i = start + 1; i <= end; i++) { if(array[i] < min) { min = array[i]; } } return min;}复制代码 21. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
这里有两种解题思路：第一种是利用插入排序的思路（其实只要能保证稳定性的排序算法都可以），遍历数组，如果该元素是奇数，则对前面的元素进行，如果前面的元素是偶数则进行交换，直到找到一个奇数为止。
第二种是借助辅助数组，首先遍历一遍数组，将所有奇数元素保存到辅助数组中，并计算出奇数元素的个数；然后再遍历一遍辅助数组，将其中所有奇数元素放到原数组的前半部分，将所有偶数元素放到从 count 开始的后半部分。
代码实现
// 时间复杂度 O(n^2)public static void reorderOddEven1(int[] data) { for (int i = 1; i < data.length; i++) { if ((data[i] & 1) == 1) { int temp = data[i]; int j = i - 1; for (; j >= 0 && (data[j] & 1) == 0; j--) { data[j + 1] = data[j]; } data[j + 1] = temp; } }}// 时间复杂度 O(n) 空间复杂度 O(n)public static void reorderOddEven2(int[] data) { if (data == null || data.length <= 0) { return; } int count = 0; int[] tempArr = new int[data.length]; for (int i = 0; i < data.length; i++) { if ((data[i] & 1) == 1) { count++; } tempArr[i] = data[i]; } int j = 0, k = count; for (int i = 0; i < data.length; i++) { if ((tempArr[i] & 1) == 1) { data[j++] = tempArr[i]; } else { data[k++] = tempArr[i]; } }}复制代码 这里第一种做法，和插入排序的时间复杂度一致，平均情况下时间复杂度为 O(n^2)，在最好情况下时间复杂度是 O(n)。
而第二种做法，由于只需要遍历两次数组，所以时间复杂度为 O(n)。但是需要借助辅助数组，所以空间复杂度是 O(n)。
29. 顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。如果输入如下 4 X 4 矩阵：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。
解题思路
在打印矩阵时，可以按照从外到内一圈一圈来打印，于是可以使用循环来打印矩阵，每次循环打印一圈。对于一个 5 * 5 的矩阵，循环结束条件是 2 * 2 < 5，而对于一个 6 * 6 的矩阵，循环结束条件是 2 * 3 < 6。所以可以得出循环结束的条件是 2 * start < rows && 2 * start < cols。
在打印一圈时，可以分为从左到右打印第一行、从上到下打印最后一列、从右到左打印最后一行、从下到上打印第一列。但是这里需要考虑最后一圈退化为一行、一列的情况。
代码实现
public ArrayListprintMatrix(int [][] matrix) { ArrayList res = new ArrayList<>(); int rows, cols; if(matrix == null || (rows = matrix.length) <= 0 || (cols = matrix[0].length) <= 0){ return res; } int i = 0; while(2 * i < rows && 2 * i < cols) { printMatrixCore(matrix, i++, res); } return res;}public void printMatrixCore(int[][] matrix, int start, ArrayList res) { int endX = matrix.length - start - 1; int endY = matrix[0].length - start - 1; // 第一行总是存在的 for(int i = start; i <= endY; i++) { res.add(matrix[start][i]); } // 至少要有两行 if(endX > start) { for(int j = start + 1; j <= endX; j++) { res.add(matrix[j][endY]); } } // 至少要有两行两列 if(endX > start && endY > start) { for(int i = endY - 1; i >= start; i--) { res.add(matrix[endX][i]); } } // 至少要有三行两列 if(endX > start + 1 && endY > start) { for(int j = endX - 1; j > start; j--) { res.add(matrix[j][start]); } }}复制代码
39. 数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。
解题思路1
由于有一个数字出现次数超过了数组长度的一半，所以如果数组有序的话，那么数组的中位数必然是出现次数超过一半的数。
但是这里没有必要完全对数组排好序。可以利用快速排序的思想，使用 partition 函数，对数组进行切分，使得切分元素之前的元素都小于等于它，之后的元素都大于等于它。
一次切分之后可以将切分元素的下标 index 与数组中间的 mid 比较，如果 index 大于 mid，表示中间值在左半部分，将 end = mid - 1，继续进行切分；而如果 index 小于 mid，表示中间值在右半部分，将 start = mid + 1，继续进行切分；否则表示找到了出现次数超过一半的元素。
代码实现1
public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length <= 0) { return 0; } int start = 0; int end = array.length - 1; int mid = (end - start) >> 1; int index = partition(array, start, end); while(index != mid) { if(index > mid) { end = index - 1; index = partition(array, start, end); } else { start = index + 1; index = partition(array, start, end); } } if(checkMoreThanHalf(array, array[index])) { return array[index]; } return 0;}public int partition(int[] array, int left, int right) { int pivot = array[left]; int i = left, j = right + 1; while(true) { while(i < right && array[++i] < pivot) { if(i == right) { break; } } while(j > left && array[--j] > pivot) { } if(i >= j) { break; } int temp = array[i]; array[i] = array[j]; array[j] = temp; } array[left] = array[j]; array[j] = pivot; return j;}public boolean checkMoreThanHalf(int[] array, int res) { int count = 0; for(int i = 0; i < array.length; i++) { if(array[i] == res) { count++; } } return count * 2 > array.length;}复制代码 解题思路2
还有一种解题思路，它是利用数组的特点，使用一个 times 来记录某个数的出现的次数，然后遍历数组，如果 times 为 0，将当前元素赋给 result，并将 times 置为 1；否则如果当前元素等于 result，则将 times 加 1，否则将 times 减 1。
如此在遍历完数组，出现次数 times 大于等于 1 对应的那个数一定就是出现次数超过数组一半长度的数。
代码实现2
public static int moreThanHalfNum(int[] number) { if (number == null || number.length <= 0) { return -1; } int result = 0; int times = 0; for (int i = 0; i < number.length; i++) { if (times == 0) { result = number[i]; times = 1; } else if (result == number[i]) { times++; } else { times--; } } if (checkMoreThanHalf(number, result)) { return result; } return -1;}private static boolean checkMoreThanHalf(int[] number, int result) { int count = 0; for (int a : number) { if (a == result) { count++; } } return count * 2 > number.length;}复制代码 这种方法只需要遍历一遍数组，就可以找到找到数组中出现次数超过一半的数，所以时间复杂度是 O(n)。虽然与前一种方法的时间复杂度一致，但无疑简洁了不少。
42. 连续子数组的最大和
题目描述
输入一个整型数组。数组里有正数和负数。数组中一个或多个连续的整数组成一个子数组，求所有子数组和的最大值。
解题思路
可以从头到尾遍历数组，如果前面数个元素之和 lastSum 小于 0，就将其舍弃，将 curSum 赋值为 array[i]。否则将前面数个元素之和 lastSum 加上当前元素 array[i]，得到新的和 curSum。然后判断这个和 curSum 与保存的最大和 maxSum，如果 curSum 大于 maxSum，则将其替换。然后更新 lastSum，继续遍历数组进行比较。
代码实现
public int findGreatestSumOfSubArray(int[] array) { if(array == null || array.length <= 0) { return -1; } int lastSum = 0; int curSum = 0; int maxSum = Integer.MIN_VALUE; for(int i = 0; i < array.length; i++) { if(lastSum <= 0) { curSum = array[i]; } else { curSum = lastSum + array[i]; } if(curSum > maxSum) { maxSum = curSum; } lastSum = curSum; } return maxSum;}复制代码 51. 数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数 P，并将 P 对 1000000007 取模的结果输出，即输出 P%1000000007。
解题思路
首先把数组分成两个子数组，然后递归地对子数组求逆序对，统计出子数组内部的逆序对的数目。
由于已经统计了子数组内部的逆序对的数目，所以需要这两个子数组进行排序，避免在后面重复统计。在排序的时候，还要统计两个子数组之间的逆序对的数目。
注意，这里如果 aux[i] > aux[j]，应该是 count += mid + 1 - i;，也就是从下标为 i ~ mid 的元素与下标为 j 的元素都构成了逆序对。而如果是 count += j - mid; 的话，则成了下标为 i 的元素与下标为 mid + 1 ~ j 的元素构成了逆序对，后面会出现重复统计的情况。
最后对两个子数组内部的逆序对和两个子数组之间的逆序对相加，返回即可。
代码实现
public int inversePairs(int [] array) { if(array == null || array.length <= 0) { return 0; } int[] aux = new int[array.length]; return inversePairs(array, aux, 0, array.length - 1);}public int inversePairs(int[] data, int[] aux, int start, int end) { if(start >= end) { return 0; } int mid = start + ((end - start) >> 1); int left = inversePairs(data, aux, start, mid); int right = inversePairs(data, aux, mid + 1, end); for(int i = start; i <= end; i++) { aux[i] = data[i]; } int i = start; int j = mid + 1; int count = 0; for(int k = start; k <= end; k++) { if(i > mid) { data[k] = aux[j++]; } else if(j > end) { data[k] = aux[i++]; } else if(aux[i] > aux[j]) { data[k] = aux[j++]; count += mid + 1 - i; count %= 1000000007; } else { data[k] = aux[i++]; } } return (left + right + count) % 1000000007;}复制代码 这种方法与归并排序的时间、空间复杂度一致，每次排序的时间为 O(n)，总共需要 O(logn) 次，所以总的时间复杂度是 O(nlogn)。在归并时需要辅助数组，所以其空间复杂度为 O(n)。
53. 在排序数组中查找数字
题目一描述
统计一个数字在排序数组中出现的次数。
解题思路
对于排序数组，可以使用两次二分查找分别找到要查找的数字第一次和最后一次出现的数组下标。然后就可以计算出该数字出现的次数。
查找第一次出现的数组下标时，如果数组中间元素大于该数字 k，则在数组左半部分去查找，否则数组中间元素小于该数字 k，则在数组右半部分去查找。
当中间元素等于 k 时，则需要判断 mid，如果 mid 前面没有数字，或者前面的数字不等于 k，则找到了第一次出现的数组下标；否则继续在数组左半部分去查找。
查找最后一次出现的数组下标与查找第一次出现的思想类似，这里就不再赘述了。
代码实现
public int GetNumberOfK(int [] array , int k) { if(array == null || array.length <= 0) { return 0; } int left = getFirstIndex(array, k); int right = getLastIndex(array, k); if(left != -1 && right != -1) { return right - left + 1; } return 0;}public int getFirstIndex(int[] array, int k) { int start = 0; int end = array.length - 1; while(start <= end) { int mid = start + ((end - start) >> 1); if(k == array[mid]) { if(mid == 0 || array[mid - 1] != k) { return mid; } else { end = mid - 1; } } else if(k < array[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1;}public int getLastIndex(int[] array, int k) { int start = 0; int end = array.length - 1; while(start <= end) { int mid = start + ((end - start) >> 1); if(k == array[mid]) { if(mid == end || array[mid + 1] != k) { return mid; } else { start = mid + 1; } } else if(k < array[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1;}复制代码 题目二描述
一个长度为 n 的递增数组中的所有数字都是唯一的，并且每个数字都在 [0, n] 范围内，在 [0, n] 范围内的 n+1 个数字中有且只有一个数字不在数组中，请找出这个数字。
解题思路
由于数组是有序的，所以数组开始的一部分数字与它们对应的下标是相等。如果不在数组中的数字为 m，则它前面的数字与它们的下标都相等，它后面的数字比它们的下标都要小。
可以使用二分查找，如果中间元素的值和下标相等，则在数组右半部分查找；如果不相等，则需要进一步判断，如果它前面没有元素，或者前面的数字和它的下标相等，则找到了 m；否则继续在左半部分查找。
代码实现
public static int getMissingNumber(int[] arr) { if (arr == null || arr.length <= 0) { return -1; } int start = 0; int end = arr.length - 1; while (start <= end) { int mid = start + ((end - start) >> 1); if (arr[mid] != mid) { // 当前不相等，前一个相等，表示找到了 if (mid == 0 || arr[mid - 1] == mid - 1) { return mid; // 左半边查找 } else { end = mid - 1; } } else { //右半边查找 start = mid + 1; } } if (start == arr.length) { return arr.length; } return -1;}复制代码 56. 数组中数字出现的次数
题目一描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思路
这里解题思路有些巧妙，使用位元素来解决，由于两个相等的数字异或后结果为 0，所以遍历该数组，依次异或数组中的每一个元素，那么最终的结果就是那两个只出现一次的数字异或的结果。
由于这两个数字肯定不一样，异或的结果也肯定不为 0，也就是它的二进制表示中至少有一位是 1，将该位求出后记为 n。
可以将以第 n 位为标准将原数组分为两个数组，第一个数组中第 n 位是 1，而第二个数组中第 n 位是 0，而两个只出现一次的数字必然各出现在一个数组中，并且数组中的元素异或的结果就是只出现一次的那个数字。
代码实现
public void findNumsAppearOnce(int [] array,int num1[] , int num2[]) { if(array == null || array.length <= 0) { return; } int num = 0; for(int i = 0; i < array.length; i++) { num ^= array[i]; } int index = bitOf1(num); int mark = 1 << index; for(int i = 0; i < array.length; i++) { if((array[i] & mark) == 0) { num1[0] ^= array[i]; } else { num2[0] ^= array[i]; } }}public int bitOf1(int num) { int count = 0; while((num & 1) == 0) { num >>= 1; count++; } return count;}复制代码 题目二描述
一个整型数组里除了一个数字只出现了一次之外，其他的数字都出现了三次。请找出那个只出现一次的数字。
解题思路
这里由于出现了三次，虽然不能再使用异或运算，但同样可以使用位运算。可以从头到尾遍历数组，将数组中每一个元素的二进制表示的每一位都加起来，使用一个 32 位的辅助数组来存储二进制表示的每一位的和。
对于所有出现三次的元素，它们的二进制表示的每一位之和，肯定可以被 3 整除，所以最终辅助数组中如果某一位能被 3 整除，那么那个只出现一次的整数的二进制表示的那一位就是 0，否则就是 1。
代码实现
public static void findNumberAppearOnce(int[] arr, int[] num) { if (arr == null || arr.length < 2) { return; } int[] bitSum = new int[32]; for (int i = 0; i < arr.length; i++) { int bitMask = 1; for (int j = 31; j >= 0; j--) { int bit = arr[i] & bitMask; if (bit != 0) { bitSum[j]++; } bitMask <<= 1; } } int result = 0; for (int i = 0; i < 32; i++) { result <<= 1; result += bitSum[i] % 3; } num[0] = result;}复制代码 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]。不能使用除法。
解题思路
这里要求 B[i] = A[0] * A[1] * ... * A[i-1] * A[i+1] * ... * A[n-1]，可以将其分为分为两个部分的乘积。
A[0] * A[1] * ... * A[i-2] * A[i-1]A[i+1] * A[i+2] * ... * A[n-2] * A[n-1]复制代码
可以使用两个循环，第一个循环采用自上而下的顺序，res[i] = res[i - 1] * arr[i - 1] 计算前半部分，第二循环采用自下而上的顺序，res[i] *= (temp *= arr[i + 1])。
代码实现
public int[] multiply(int[] arr) { // arr [2, 1, 3, 4, 5] if (arr == null || arr.length <= 0) { return null; } int[] result = new int[arr.length]; result[0] = 1; for (int i = 1; i < arr.length; i++) { result[i] = arr[i - 1] * result[i - 1]; } // result [1, 2, 2, 6, 24] int temp = 1; for (int i = result.length - 2; i >= 0; i--) { temp = arr[i + 1] * temp; result[i] = result[i] * temp; } // temp 60 60 20 5 1 // result [60, 120, 40, 30, 24] return result;}复制代码