剑指Offer学习 找出数组中重复的数字

剑指Offer的学习记录,Java语言

问题

在一个长度为n的数组里的所有数字都在0n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2

理解

看到这种找重复数字的题目,第一反应是先将数组排序,然后在已序数组中查找重复数字。排序一个长度为n的数组需要$O(nlogn)$的时间,之后再遍历数组。

同样,我们也可以利用哈希表来解决这个问题。从头到尾按顺序扫描原数组,每扫描一个数字,判断哈希表中是否存在该数字,若没有该数字,就将数字加入哈希表中,若哈希表中已存在该数字,则就找到一个重复数字。

当然,今天所要讲解的方法并不是以上两个。

我们注意到,数组中的数字都在0~n-1范围内。如果这个数组中没有重复的数字,那么当数组排序后,数字i就会出现在索引为i的位置上。但是现在是数组中有重复的数字,有些位置上可能存在多个数字,有些位置上没有数字。

从头到尾扫描这个数组中的每个数字,当扫描到下标为i的数字时,

  • 首先比较这个数字(记为m)和i是否相等,若相等,接着扫描下一个数字;
  • 若不相等,则将m与索引为m上的数字进行比较。
    • 如果它与第m个数字相等,就找到了一个重复的数字;
    • 若不相等,则将第i个数字和第m个数字交换,把m放在属于它的位置上。
  • 接下来便是重复比较下去,直到发现一个重复的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个,赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (length <= 0 || numbers == null)
return false;
for (int i = 0; i < length; i++) {
while (i != numbers[i]) {
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i]; //重复的数字
return true;
}
swap(numbers, i, numbers[i]);
}
}
return false;
}
//交换i和m(j)上的数字
public void swap(int numbers[], int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
------------- 本 文 结 束 感 谢 您 的 阅 读 -------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%