剑指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 | public int findRepeatNumber(int[] nums) { |
复杂度分析
时间复杂度:O(n) 遍历整个数组
空间复杂度:O(n) 使用辅助空间Set。
方法二:交换数组位置
由于数组是0~n-1,这个范围恰巧可以与数组的下标一一对应,所以nums[i]的值为下标i的位置,
因此本身数组可以作为哈希表来进行使用。
遍历数组,当数组元素对应则进行下一轮,如果此时下标nums[i]的值为nums[i],则表示有冲突,就意味着找到重复的值,返回即可。如果没有冲突,则将nums[i]的值交换到对应的位置上。
代码实现:
1 | public int findRepeatNumber2(int[] nums) { |
复杂度分析
时间复杂度:O(n) 遍历整个数组
空间复杂度:O(1) 原地算法。
方法三:排序
排序,比较相邻的元素是否相等
代码实现:
1 | public static int findRepeatNumber3(int[] nums) { |
复杂度分析
时间复杂度: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
剑指Offer 03.数组中重复的数字【哈希表、数组交换、排序】
install_url
to use ShareThis. Please set it in _config.yml
.