这个题有多种思路。
- 使用Hash来解决问题。
在这个算法中,我们使用了一个辅助数组,数组中的元素是boolean类型,数组中元素的值用以表示某个值是否出现过。如果出现过,那么它的状态就设置为true。
Java代码的实现如下:
class findDuplicate { public static int findDuplicate(int arr[]) { int n = arr.length; // 创建一个数组visited,用来存储是数字否存在的标志 // 也可以使用map代替 boolean visited[] = new boolean[n + 1]; // 遍历数组中的每个元素,并标志访问过的数据为true // 如果元素之前出现过,则返回这个元素 for (int i = 0; i < n; i++) { if (visited[arr[i]]) { return arr[i]; } visited[arr[i]] = true; } // 没找到 return -1; } public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 4 }; System.out.println(findDuplicate(arr)); } }
这种算法的时间复杂度是O(n),空间复杂度也是O(n)。
- 我们还能使用常量空间(空间复杂度为O(1))解决问题。既然数组中除了一个元素是重复之外,其他元素都是唯一的,并且元素的值在 1 到 n-1 之间,我们可以把数组的下标作为key,把元素取负数来判断元素是否重复。例如,对于每个元素 arr[i],我们得到它的绝对值 abs(arr[i]),并修改下标为 abs(arr[i]) – 1 的这个元素的正负号。最后,我们再遍历一次数组,如果第 i 个元素的值是正数,那么重复的元素就是 i + 1。
上面的算法我们遍历了2次数组。其实,我们可以缩为1次。对于每一个元素 arr[i],我们得到绝对值abs(arr[i]),然后反转第abs(arr[i])-1个元素的符号,如果准备反转符号的元素已经是负数了,那么它一定是那个重复的数字。
Java代码实现如下(此处我们只实现findDuplicate方法,不再重新创建类):
public int findDuplicate(int arr[]) { int n = arr.length; int duplicate = -1; for (int i = 0; i < n; i++) { int absVal = (arr[i] < 0) ? -arr[i] : arr[i]; // 如果数组中,下标为 abs(arr[i]) - 1 的元素为正数,那么改变成负数 if (arr[absVal - 1] >= 0) { arr[absVal - 1] = -arr[absVal - 1]; } else { // 如果已经是负数,说明它是重复元素 duplicate = absVal; break; } } // 恢复数组到初始值 for (int i = 0; i < n; i++) { if (arr[i] < 0) { arr[i] = -arr[i]; } } return duplicate; }
这种算法的时间复杂度是O(n),空间复杂度是O(1)。
- 这种方法和方法2类似。这种方案是对数组通过交换位置的方式进行从小到大的排序。因为数字是连续的,所以数组的第 i 个位置的值是 i + 1。在排序的过程中,如果要交换的两个数字是相等的,那么它就是重复的。
遍历数组,对于第 i 个元素:
- 如果它的值为 arr[i] 等于 i + 1,那么继续遍历下一个元素;
- 如果 arr[i] 等于 arr[arr[i] – 1 ],那么它就是重复的数字;
- 如果不满足前面两个条件,则交换 arr[i] 与 arr[arr[i] – 1] 的值。
但这种方案会改变原始数组的内容,且无法恢复。当然,原题并没有提到不允许改变原始数据,这是常见编程规范的约定。相对而言,并没有方法2好,不推荐。
Java代码实现如下:
public int findDuplicate(int arr[] ) { int num = 0; int index = 0; int len = arr.length; while (index < len) { num = arr[index]; // 如果位置的值等于自己本身,那么跳到下一个 if (num == index + 1) { index++; continue; } // 如果数值重合,则返回 if (arr[num - 1] == num) { return num; } // 交换位置 arr[index] = arr[num - 1]; arr[num - 1] = num; } // 不会执行到这一步 return -1; }
- 使用异或。
还可以使用异或(XOR)来解决问题。思路就是把所有的元素 1 到 n-1 的数都异或一次,由于a^a = 0, 0^0 = 0,a^0 = a。在这个异或中,重复的元素出现了3次,其他所有的元素都出现了2次,所以最后的值就是重复的元素。
Java代码实现如下:
public int findDuplicate(int arr[]) { int n = arr.length; int XOR = 0; for (int i = 0; i < n; i++) { XOR ^= A[i]; } for (int i = 1; i <= n - 1; i++) { XOR ^= i; } return XOR; }
这种算法的时间复杂度是O(n),空间复杂度是O(1)。
- 求和。
我们可以通过求和的方式解决问题:先计算出所有元素的和,然后再减去1到n-1的和,最后的值就是重复的数。这种方案最简单。
Java代码实现如下:
public int findDuplicate(int arr[]) { int size = arr.length; // int 会存在越界的情况,所以要转换成 long // long 一定不会越界 long expected_sum = ((long) size) * (size - 1) / 2; long actual_sum = 0; for (int i = 0; i < size; i++) { actual_sum += arr[i]; } return (int) (actual_sum - expected_sum); }
这种算法的时间复杂度是O(n),空间复杂度是O(1)。
备注:本题来自《(4/500)从有限范围的数组中找出重复元素》,此次重新整理,进一步完善算法。
请你留言