youyichannel

志于道,据于德,依于仁,游于艺!

0%

四种方法带你解决「寻找重复数」

前情提要

数组可以说是最简单的一种数据结构,它占据一块连续的内存并按照顺序存储数据。创建数组时,需要指定数组的容量大小,然后根据大小分配内存。

存在的问题:空间效率不是很好。即使只在数组中存储一个数字,也需要为所有的数据预先分配内存,于是乎经常会有空闲的区域没有得到充分利用。

优势:由于数组的内存是连续的,于是可以根据下标在O(1)的时间内读写任何元素,因此时间效率是很高的。

⚠️注意:

  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的

为了解决数组空间效率不高的问题,人们又提出并实现了多种动态数组,在这里不再赘述。

寻找重复数

题目对应链接

给定一个包含 n 个整数的数组 nums ,其数字都在 [0, n-1] 范围内,可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,返回 这个重复的数

方法一:排序

解决这个问题的一个简单方法就是把输入的数组排序,然后遍历查找即可。

排序一个数组的时间复杂度是 O(nlogn)

class Solution {
public int findDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i = 1; i < nums.length; i++) {
if(nums[i - 1] == nums[i]) return nums[i];
}
return -1;
}
}
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)

方法二:哈希表

还可以利用哈希表来解决这个问题,从头到尾按顺序遍历数组的每个元素,每扫描到一个元素时,都可以利用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字,就把它加入到哈希表;如果哈希表中已经存在了这个元素,就说明找到了答案。

class Solution {
public int findDuplicate(int[] nums) {
int[] hash = new int[nums.length];
for(int x : nums) {
if(hash[x] != 0) return x;
hash[x]++;
}
return -1;
}
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法三:原地交换

注意到数组中的数字都在 [0, n - 1] 范围内,如果这个数组中没有重复的数值,那么当数组排序之后数字 i 将出现在下标为 i 的位置上。由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。

做法:重排数组。从头到尾依次扫描这个数组中的每个数字。当扫描到下标为 i 的数字时,首先比较这个数字 m 是不是等于 i, 如果是,接着扫描下一个数字;如果不是,则再拿它和第m个数字进行比较。如果它和第 m个数字相等,就找到了一个重复的数字,因为该数字在下标 im 的位置都出现了;如果它和第 m 个数字不相等,就把第 i 个数字和第 m 个数字交换,把 m 放到属于它的位置上。重复这个比较、交换的过程,直到发现第一个重复的数字。

举例:

nums = [2, 3, 1, 0, 2, 5, 3]
turn1: [1, 3, 2, 0, 2, 5, 3]
turn2: [3, 1, 2, 0, 2, 5, 3]
turn3: [0, 1, 2, 3, 2, 5, 3]
turn4: => ans = 2

代码:

class Solution {
public int findDuplicate(int[] nums) {
for(int i = 0; i < nums.length; i++) {
while(nums[i] != i) {
if(nums[i] == nums[nums[i]]) return nums[i];

// swap
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return -1;
}
}
  • 时间复杂度:O(n),因为每个数字最多只要交换两次就能找到它的位置
  • 空间复杂度:O(1)

接下来我们提出一个要求:不修改数组,找出重复的数字,同时数组的范围变为了[1,n],一共 n+1 个数。

最简单的做法肯定是复制一份原始数组,然后就和上面说的一样了。

方法四:二分

核心重点的是理解在某个范围中的数字的个数

把从 1~n 的数字从中间的数字 m 分为两部分,前面一半为 1~m, 后面一半为 m+1~n,如果 1~m 的数字的数目超过 m,那么这一半的区间里一定包含重复的数字;否则另一半 m+1~n 的区间里一定包含重复的数字。可以继续把包含重复数字的区间一分为二,直到找到一个重复的数字。

举例:

nums = [2, 3, 5, 4, 3, 2, 6, 7]
turn1: m = 4 => [2, 3, 4, 3, 2], [5, 6, 7] => 1~4 这四个数出现五次,因此这四个数中一定存在重复的数字
turn2: 再把 1~4 范围一分为二,m=2, 统计 => 3~4 范围中的数字出现了三次,意味着 3、4两个数字中一定有一个数字重复了。再分别统计这两个数字在数组中出现的次数,得出答案为3

代码:

class Solution {
public int findDuplicate(int[] nums) {
int length = nums.length;
int start = 1, end = length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
int count = countRange(nums, start, mid);

if(end == start) {
if(count > 1) return start; // 找到重复的数字
else break;
}

if(count > (mid - start + 1)) // 重复的数字在 [start, mid] 中
end = mid;
else // 重复的数字在 [mid + 1, end] 中
start = mid + 1;
}
return -1;
}
int countRange(int[] nums, int start, int end) {
int count = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] >= start && nums[i] <= end)
count++;
}
return count;
}
}
  • 时间复杂度:O(nlogn),如果输入长度为n的数组,那么函数countRange将被调用O(logn)次,每次需要O(n)的时间,因此总的时间复杂度是O(nlogn)
  • 空间复杂度:O(1)

好了,到此结束,四种思路,希望能够帮到你打开思路。我是youyi,我们下次见啦~