2

找出数组中重复的数字

 2 years ago
source link: https://zhangslob.github.io/2019/12/26/%E6%89%BE%E5%87%BA%E6%95%B0%E7%BB%84%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E6%95%B0%E5%AD%97/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client 
这是崔斯特的第一百零八篇原创文章

努力、奋斗 (๑• . •๑)

找出数组中重复的数字

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

排序后，顺序扫描，判断是否有重复，时间复杂度为 O(n²)。

利用哈希表，遍历数组，如果哈希表中没有该元素，则存入哈希表中，否则返回重复的元素。时间复杂度为 O(n)，空间复杂度为 O(n)。

长度为 n，元素的数值范围也为 n，如果没有重复元素，那么数组每个下标对应的值与下标相等。

从头到尾遍历数组，当扫描到下标 i 的数字 nums[i]：

  • 如果等于 i，继续向下扫描；
  • 如果不等于 i，拿它与第 nums[i] 个数进行比较，如果相等，说明有重复值，返回 nums[i]。如果不相等，就把第 i 个数 和第 nums[i] 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 O(n)，因为每个元素最多只要两次交换，就能确定位置。空间复杂度为 O(1)。

* @author zhujian on 2019/12/26.
public class Solution {
public int findDuplicate(int[] array) {
if (array.length == 0) {
return -1;
for (int i = 0; i < array.length; i++) {
while (array[i] != i) {
if (array[i] == array[array[i]]) {
return array[i];
swap(array, i, array[i]);
System.out.println(Arrays.toString(array));
return -1;
private void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 1, 0, 2, 5, 3};
int res = new Solution().findDuplicate(arr);
System.out.println(res);

代码中有一个两重循环，但每个数字最多只要交换两次就可以找到属于自己的位置，因此时间复杂度是O(n)。不需要额外分配内存，空间复杂度是O(1)。

Output

[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]

以数组[2, 3, 1, 0, 2, 5, 3]为例来分析找到重复数字的步骤：

  1. 数组的第 0 个数字（从 0 开始计数，和数组的下标保持一致）是 2，与它的下标不相等，于是把它和下标为 2 的数字 1 交换。交换之后的数组是[1, 3, 2, 0, 2, 5, 3]。
  2. 此时第 0 个数字是 1，仍然与它的下标不相等，继续把它和下标为 1 的数字 3 交换，得到数组[3, 1, 2, 0, 2, 5, 3]
  3. 接下来继续交换第 0 个数字 3 和第 3 个数字 0，得到数组[0, 1, 2, 3, 2, 5, 3]。
  4. 此时第 0 个数字的数值为 0，接着扫描下一个数字。在接下来的几个数字中，下标为 1，2，3 的三个数字分别为 1，2，3 它们的下标和数值都分别相等，因此不需要做任何操作。
  5. 接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等，再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2，也就是数字在下标为 2 和下标为 4 的两个位置都出现了，因此找到一个重复的数字。

本题关键是：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内并且有重复，这说明数组是可以排序的，把每个数字交换到自己应该在的位置，排序时就能找到重复字段。理想状态下的情况：[0, 1, 2, 3, 4, x, x, x]

Python解法更简单

def solution(arr):
if len(arr) == 0:
return -1
for i in range(len(arr)):
while arr[i] != i:
tmp = arr[i]
if tmp == arr[tmp]:
return tmp
arr[i], arr[tmp] = arr[tmp], arr[i]
print(arr)
print(solution([3, 1, 2, 0, 2, 5, 3]))

不修改数组找出重复的数字

在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内，数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字 2 或者 3。

创建长度为 n+1 的辅助数组，把原数组的元素复制到辅助数组中。如果原数组被复制的数是 m，则放到辅助数组第 m 个位置。这样很容易找出重复元素。空间复杂度为 O(n)。

数组元素的取值范围是 [1, n]，对该范围对半划分，分成 [1, middle], [middle+1, n]。计算数组中有多少个(count)元素落在 [1, middle] 区间内，如果 count 大于 middle，那么说明这个范围内有重复元素，否则在另一个范围内。继续对这个范围对半划分，继续统计区间内元素数量。

时间复杂度 O(n * log n)，空间复杂度 O(1)。

注意，此方法无法找出所有重复的元素。如果左右半区同时存在重复值，先算哪个半区就会先得到哪边的重复值。

* @author zhujian on 2019/12/26.
public class Solution {
public int findDuplicate(int[] array) {
if (array.length == 0) {
return -1;
int start = 1;
int end = array.length - 1;
while (start <= end) {
int middle = start + ((end - start) >> 1);
int count = countRange(array, start, middle);
if (end == start) {
if (count > 1) {
return start;
} else {
break;
} else {
if (count > (middle - start) + 1) {
end = middle;
} else {
start = middle + 1;
return -1;
private int countRange(int[] array, int start, int end) {
if (array.length == 0) {
return -1;
int count = 0;
for (int i : array) {
if (i >= start && i <= end) {
count++;
return count;
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 5, 4, 3, 2, 6, 7};
int res = new Solution().findDuplicate(arr);
System.out.println(res);

按照二分法查找的思路，如果输出长度为n的数组，那么函数countRange将被调用O(log n)次，每次需要O(n)时间，因此总的时间复杂度是O(nlog n) ，空间复杂度是O(1)。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK