面试题3_第一题: 找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
三种方法解答：
public class DuplicateInArray {
// 思路1：排序，排序后查找数组中是否重复很简单了。
// 时间复杂度时nlog(n)
public static int solution(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] < 0 || nums[i] > len - 1) return -1;
}
Arrays.sort(nums);
for (int i=0; i < len - 1; i++) {
if (nums[i] == nums[i+1])
return nums[i];
}
return -1;
}
// 思路2：利用哈希表，加入时看是否存在，存在则返回
// 时间复杂度时 n ,空间复杂度是 n
public static int solution2(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num))
return num;
}
return -1;
}
// 思路3: 它是0 - n-1 之间的数字，那么对应就和数组下标一致。
// 遍历数组，当数字与下标不一致，就去跟以此数为下标的数去进行交换，如果不一致就交换，如果一致，可以之间返回此数
public static int solution3(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] < 0 || nums[i] > len - 1) return -1;
}
int tmp ;
for (int i = 0; i < len; i++) {
while (i != nums[i]) {
if (nums[i] != nums[nums[i]]) {
tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}else return nums[i];
}
}
return -1;
}
public static void main(String[] args) {
int []nums = new int[]{2,3,1,0,2,5,3};
System.out.println(solution3(nums));
}
}
面试题3_第二题: 不修改数组，找出数组中重复的数字
在一个长度为n+1的数组里得所有数字都在1~n的范围内。所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，输入长度为8的数组{2,3,5,4,3,2,6,7}那么对应的输出是重复的数字2或者3。
public class DuplicatInArrayNoEdit {
// 思路1：因为题目是 1-n 的区间，没有0，很好在另一个数组中判断。
// 弄一个长度为 n 的数组，复制到数字为下标的地方，如果已经存在，则重复
// 时间复杂度为O(N)，空间复杂度也为O(N)
public static int solution1(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] < 1 || nums[i] > len) return -1;
}
int[] newArr = new int[len];
for (int i = 0; i < len; i++) {
if (newArr[nums[i]] == 0)
newArr[nums[i]] = nums[i];
else return nums[i];
}
return -1;
}
// 思路2: 二分查找的思路
// 将数组分成两部分，1-m 和 m+1 - n,如果1-m 中包含的数超过 m 个，则中间有重复的，否则另一半中有重复。
// 主要是二分 ， 然后看某一半中的数字的量
// 二分的时间复杂度是log(n), 每次二分后需要遍历一遍数组，就是 n
// 时间复杂度 nlog(n)
public static int solution2(int[] nums) {
int len = nums.length;
int start = 0,mid,end =len;
while (start <= end) {
mid = ((end - start) >> 1) + start;
//求区间中数字量
int count = countRange(nums,len,start,mid);
if (start == end) {
if (count > 1) return start;
else break;
}
if (count > (mid - start + 1))
end = mid ;
else start = mid + 1;
}
return -1;
}
private static int countRange(int[] nums, int len, int start, int end) {
int cnt = 0;
for (int i = 0; i < len; i++) {
//在区间的++
if (nums[i] >= start && nums[i] <= end)
cnt++;
}
return cnt;
}
public static void main(String[] args) {
int []nums = new int[]{2,3,1,6,2,5,3};
System.out.println(solution2(nums));
}
}