最近在用Java刷剑指offer（第二版）的面试题。书中原题的代码采用C++编写，有些题的初衷是为了考察C++的指针、模板等特性，这些题使用Java编写有些不合适。但多数题还是考察通用的算法、数据结构以及编程思想等，与语言本身无太大关系。因此在选择编程语言时，我还是选择了Java。好吧，主要是我C++不怎么会，仅仅是曾经学过俩月，使用Java顺手一些。后续可能再用Python刷一遍。
面试题3 数组中重复的数字题目一：找出数组中重复的数字
描述：在长度为n的数组里所有数字都在0~n-1范围内。数组中某些数字是重复的，请找出任意一个重复的数字。如数组｛2, 3, 1, 0, 2, 5, 3｝，输出的重复的数字为2或3。
思路：利用数组的索引在0~n-1这个范围的性质，将数字i移至索引i的位置。
考点：对数组的理解以及对问题的分析能力。
题目二：不修改数组找出重复的数字
描述：在长度为n+1的数组里所有数字都在1~n范围内。找出重复的数字，但不修改数组。
思路：当然可完全利用题目一的方法，只是需要辅助空间。不需要辅助空间是最好的了。这里使用二分法，对数组进行计数，逐渐缩小重复的数字所处的范围。
考点：对二分查找的灵活应用，毕竟写出正确无误的二分法时有些难度的。同时要重视与面试官的沟通，明确需求，如是否能更改数组，是否可以使用辅助空间等。
package sword_offer; //page 39 数组中重复的数字 public class Solution3 { //题目1 //输出数组中重复的数字，空间复杂度O(1)，时间复杂度O(n) //数组长度为n，数字在0~n-1范围内 public static int duplicate(int[] arr) { for (int i = 0; i < arr.length; i++) { //System.out.println(i); while (arr[i] != i) { if (arr[i] == arr[arr[i]]) return arr[i]; else { int temp = arr[i]; arr[i] = arr[temp]; arr[temp] = temp; //System.out.println(Arrays.toString(arr)); } } } return -1; } //题目2 //输出数组中重复的数字，空间复杂度O(1)，时间复杂度O(nlog(n)) //数组长度为n+1，数字在1~n范围内，要求不修改数组，并不使用辅助空间 public static int myGetDuplication(int[] arr) { int start = 1; int middle = arr.length / 2; int end = middle; while(end >= start) { //System.out.println("" + start + end); int count = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] >= start && arr[i] <= end) count++; } if (end == start) { if (count > 1) return start; else break; } if (count > end - start + 1) { middle = (start + end) / 2; end = middle; } else { start = middle + 1; end = arr.length - 1; } } return -1; } //输出数组中重复的数字，空间复杂度O(1)，时间复杂度O(nlog(n)) //数组长度为n+1，数字在1~n范围内，要求不修改数组，并不使用辅助空间 //比上一个函数逻辑清晰一点 public static int getDuplication(int[] arr) { int start = 1; int end = arr.length - 1; while(end >= start) { int middle = (end - start) / 2 + start; int count = getCount(arr, start, middle); if (end == start) { if (count > 1) return start; else break; } if (count > middle - start + 1) { end = middle; } else start = middle + 1; } return -1; } //计算数组arr元素处在[start, end]范围内元素个数 private static int getCount(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; } //测试 public static void main(String[] args) { int[] arr = {1, 2, 3, 1}; System.out.println(duplicate(arr)); int[] arr2 = {2, 3, 5, 4, 3, 2, 6, 7}; System.out.println(myGetDuplication(arr2)); int[] arr3 = {2, 3, 5, 4, 3, 2, 6, 7}; System.out.println(getDuplication(arr3)); } }