剑指 03— 数组中重复的数字

Java架构师必看

修改于 2023-09-25 08:19:11

66500

代码可运行

文章被收录于专栏：Java架构师必看Java架构师必看

运行总次数：0

代码可运行

剑指 Offer 03. 数组中重复的数字

难度简单372

找出数组中重复的数字。

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

示例 1：

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

方法一:

利用set集合,如每次添加的时候判重

class Solution {
   
    public int findRepeatNumber(int[] nums) {
   
  Set<Integer> set=new HashSet<>();
        for (int num:nums){
   
            if (!set.contains(num)){
   
                set.add(num);
            }else {
   
                return num;
            }
        }
        return 0;
    }
}

复杂性分析

时间复杂度：O(n)

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

空间复杂度：O(n)。

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

方法二: 原地置换法

注意:数字的范围与数组的长度相同,我们可以把数组看成哈希表
把数组的索引看成哈希表的kye,数组的元素看成哈希表的值val
把值为val的元素放在键也为val的位置上，也就是哈希表键值对的映射关系为key == val
如果当前数字 nums[i] 和索引 i 不相等，那么应该把 nums[i] 放在索引也为 nums[i] 的位置去，就把索引为 nums[i] 和 i 的数字对换
如果数组在索引为 nums[i] 位置的数在交换前就已经是 nums[i]，说明nums[i]是重复数字，返回nums[i]
如果交换后在 nums[i] 仍然不等于 i，要继续交换，这是使用while循环的原因

    public int findRepeatNumber2(int[] nums) {
   
        for (int i = 0; i < nums.length; i++) {
   
            if (i == nums[i]) {
   
                continue;
            }
            if (nums[i] == nums[nums[i]]) {
   
                return nums[i];
            }
            //交换
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
            //这里的i--是为了抵消掉上面的i++，
            //交换之后需要原地再比较
            i--;
        }
        return -1;
    }