LeetCode 找出数组中重复的数字

简介: LeetCode 找出数组中重复的数字

题目描述:


找出数组中重复的数字。

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

示例

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

限制:2 <= n <= 100000

思路:

方法一:遍历数组


遍历整个数组,找到任意一个重复的数字,即返回。且当为了判断一个数字是否重复遇到,使用集合存储已经遇到的数字,如果遇到的数字已经在集合中,则当前的数字是重复数字。


时间复杂度:O(n)。

遍历数组一遍。使用哈希集合(HashSet),添加元素的时间复杂度为 O(1),故总的时间复杂度是 O(n)。


空间复杂度:O(n)。

不重复的每个元素都可能存入集合,因此占用 O(n) 额外空间。


Java语言版本


class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>(); 
        //数组中已遍历的要存入的集合
        int repeat = -1; //如果找到重复的返回值
        for (int num : nums) { 
            if (!set.add(num)) { //如果放入集合失败,则查找到重复的
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

方法二:哈希表冲突(修改数组)


由题意可以看出:数组 nums 里的所有数字都在 0~n-1 的范围内


那么可以,将下标与数组中的值一一对应。即看到数值,就知道它应该在下标对应的位置,即数字num[i]应该放在 i 的位置上,这就像数据结构中人为编写的哈希函数。而重复的数即哈希冲突。


算法流程:

●遍历数组 nums ,设索引初始值为 i = 0:

若 nums[i] == i : 说明此数字已在对应索引位置,无需交换,因此执行 i += 1 与 continue ;

若 nums[nums[i]] == nums[i] : 说明索引 nums[i] 处的元素值也为 nums[i],即找到一组相同值,返回此值 nums[i];

否则: 当前数字是第一次遇到,因此交换索引为 i 和 nums[i] 的元素值,将此数字交换至对应索引位置。

●若遍历完毕尚未返回,则返回 -1,代表数组中无相同值。


复杂度分析:

●时间复杂度:O(N),这里 N 是数组的长度。虽然 for 循环里面套了 while,但是每一个数来到它应该在的位置以后,位置就不会再变化。这里用到的是均摊复杂度分析的方法:如果在某一个位置 while 循环体执行的次数较多,那么一定在后面的几个位置,根本不会执行 while 循环体内的代码,也就是说最坏的情况不会一直出现。也就是说最坏复杂度的情况不会一直出现。

●空间复杂度:O(1)。


Python语言版本


class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:  //值在它该在的位置上
                i += 1
                continue
            if nums[nums[i]] == nums[i]: return nums[i]  //哈希冲突
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]] //交换
        return -1


相关文章
|
27天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
35 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
3月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
22天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
17 4
|
22天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
13 0
Leetcode第三十三题(搜索旋转排序数组)
|
22天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
47 0