本文目录
数组中的重复数字
题目描述
长度为 n 的数组里,所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为 7 的数组{2,3,1,0,2,5,3}
,那么对应的输出是重复的数字 2 或者 3。(牛课网这里弄成「那么对应的输出是第一个重复的数字 2」了)
A 简单实现思路
借助外部数组 b,原数组中的数字记为外部数组的下标,外部数组的值来存储这个数字出现的次数。原数组中的数字都在 0 到 n-1 的范围内,因此外部数组 b 的长度为 n 即可。
public boolean duplicate(int[] numbers, int length, int[] duplication) {
if (numbers == null) {
return false;
}
int[] array = new int[length];
for (int i = 0; i < length; i++) {
if (array[numbers[i]] > 0) {
duplication[0] = numbers[i];
return true;
}
array[numbers[i]]++;
}
return false;
}
时间复杂度 O(n),空间复杂度 O(n)
B 剑指 Offer 思路
如果数组中没有重复的数字,排序后第 i 个位置会存放值为 i 的数字。因为数组中某些数字是重复的,在排序后,某个位置处会存放多个相同数字(逻辑上的,就相当于叠起来),有些位置就没有数字。前者就是我们要找的数字。但是我们并不去排序,只是利用这种思想,把值为 i 的元素放到下标为 i 的位置。
具体来说,我们从前往后依次遍历该数组。当遍历到下标 i 时,记该位置上的数字为 x,如果 x 等于 i,就跳过。如果 x 不等于 i,就判断 x 应放位置处(即下标 x 处)的数字(计作 m)是否已经是 x 了,如果是就找到了一个重复的数字(循环结束);如果 m 不等于 x,那么就交换下标 i、x 的两个数(保证把位置 i 处的 x 放置到正确的位置上),直到 x 等于 i。
/**
* 将值为 i 的元素调整到下标为 i 的位置,如果该位置上的数已经等于 i 了,就说明 i 已经重复了
* @param numbers
* @param length
* @param duplication
* @return
*/
public static boolean jz(int[] numbers, int length, int[] duplication) {
for (int i = 0; i < length; i++) {
//下标 i 处的数 numbers[i],若不与下标 i 相等,就把 numbers[i] 放到下标 numbers[i] 处
while (numbers[i] != i) {
//在交换位置之前还要检查下标 numbers[i] 处的数字是否已经是 numbers[i],如果是就已经找到了重复的数字
if (numbers[numbers[i]] == numbers[i]) {
duplication[0] = numbers[i];
//注意这里不是 break
return true;
}
//交换下标为 i、numbers[i] 两个位置上的数字(保证值为 numbers[i] 的元素放到下标 numbers[i] 处)
swap(numbers, i, numbers[i]);
}
}
return false;
}
/**
* 交换下标为 i、j 的两个数
* @param numbers
* @param i
* @param j
*/
public static void swap(int[] numbers, int i, int j) {
int swap = numbers[i];
numbers[i] = numbers[j];
numbers[j] = swap;
}