剑指Offer 03.数组中重复的数字【哈希表、数组交换、排序】

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:[2, 3, 1, 0, 2, 5, 3]

输出:2 或 3

限制:

2 <= n <= 100000

解题思路

方法一:哈希表(Set)

使用哈希表来进行,遍历数组,询问哈希表是否存在num元素,如果存在返回重复数字num,否则将num加入到哈希表中

代码实现

1
2
3
4
5
6
7
8
9
10
11
public  int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return num;
} else {
set.add(num);
}
}
return -1;
}

复杂度分析

时间复杂度:O(n) 遍历整个数组

空间复杂度:O(n) 使用辅助空间Set。

方法二:交换数组位置

由于数组是0~n-1,这个范围恰巧可以与数组的下标一一对应,所以nums[i]的值为下标i的位置,

因此本身数组可以作为哈希表来进行使用。

遍历数组,当数组元素对应则进行下一轮,如果此时下标nums[i]的值为nums[i],则表示有冲突,就意味着找到重复的值,返回即可。如果没有冲突,则将nums[i]的值交换到对应的位置上。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public  int findRepeatNumber2(int[] nums) {
int len = nums.length;
int i = 0;
while (i < len) {//一直比较下标i位置的元素,只能下标i对应上了才i++。
System.out.println(i);
if (nums[i] == i) {
i++;
continue;
}
if (nums[nums[i]] == nums[i]) {
return nums[i];
}
swap(nums, i, nums[i]);
//System.out.println(Arrays.toString(nums));观察数组变换
}
return -1;
}
//a,b为下标
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}

复杂度分析

时间复杂度:O(n) 遍历整个数组

空间复杂度:O(1) 原地算法。

方法三:排序

排序,比较相邻的元素是否相等

代码实现:

1
2
3
4
5
6
7
8
9
10
public static int findRepeatNumber3(int[] nums) {
Arrays.sort(nums);
int len=nums.length;
for(int i=1;i<len;i++){
if(nums[i]==nums[i-1]){
return nums[i];
}
}
return -1;
}

复杂度分析

时间复杂度:O(nlogn) 排序算法O(nlogn)

空间复杂度:O(1) 原地算法。

注:思考,为什么不能利用方法二中的一一对应的关系来进行比较nums[i]==i来确定是否在对应的位置;
答:反例[1,2,2,3,4,5] 如果是比较一一对应关系,那么返回的结果会是1,由于数组缺失元素,排序后不能保证元素一一对应关系。

资源

《剑指offer》

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/tong-de-si-xiang-by-liweiwei1419/

剑指Offer 03.数组中重复的数字【哈希表、数组交换、排序】

http://example.com/2021/03/25/03 数组中重复的数字/

Author

John Doe

Posted on

2021-03-25

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.