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

快来打我* 2022-11-13 04:26 51阅读 0赞

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

*  题目难度：简单
 *  方法一：哈希表 / Set
 *  方法二：原地交换

> 链接：[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]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：简单 #

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

相关标签

数组、哈希表

模板

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
    
        }
    }

# 方法一：哈希表 / Set #

利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。

整体思路：

*  使用 HashSet 来进行处理，因为 HashSet 本身不允许出现重复元素，所以当添加元素失败或已经包含该数字时，则表示出现了重复元素，将其返回即可

算法流程：

1.  初始化： 新建 `HashSet` ，记为 `dic`；
2.  遍历数组 `nums` 中的每个数字 `num`：
    
    1.  当 `num` 在 `dic` 中，说明重复，直接返回 `num`；
    2.  将 `num` 添加至 `dic` 中；
3.  返回 `-1` 。本题中一定有重复数字，因此这里返回多少都可以。

复杂度分析：

*  时间复杂度  O ( N ) O(N) O(N) ： 遍历数组使用  O ( N ) O(N) O(N) ，HashSet 添加与查找元素皆为  O ( 1 ) O(1) O(1) 。
 *  空间复杂度  O ( N ) O(N) O(N) ： HashSet 占用  O ( N ) O(N) O(N) 大小的额外空间。

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
    //            HashSet<Integer> set = new HashSet<>();
    //            for (int num : nums) {
        
    //                //发现某元素存在，返回
    //                if (set.contains(num)) {
        
    //                    return num;
    //                }
    //                //存入哈希表
    //                set.add(num);
    //            }
    //            return -1;
    
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
        
                //发现某元素存在，返回
                if (set.contains(nums[i])) {
        
                    return nums[i];
                }
                //存入哈希表
                set.add(nums[i]);
            }
            return -1;
        }
    }

# 方法二：原地交换 #

从题目描述中我们可以看出，因为所有数字都在 `0 ～ n-1` 的范围内，其实完全可以省掉额外的空间开辟，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字

这本质还是哈希的思想，思路 1 是使用库函数申请额外空间，思路 2 则是数组本身做哈希表，达到了节省空间的目的

此说明含义：数组元素的 索引 和 值 是 一对多 的关系。

因此，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 `nums[i] = i`）。因而，就能通过索引映射对应的值，起到与字典等价的作用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
遍历中，第一次遇到数字 `x` 时，将其交换至索引 `x` 处；而当第二次遇到数字 `x` 时，一定有 `nums[x] = x`，此时即可得到一组重复数字。

算法流程：

1.  遍历数组 `nums` ，设索引初始值为 `i = 0` :
    
    1.  若 `nums[i] = i` ： 说明此数字已在对应索引位置，无需交换，因此跳过；
    2.  若 `nums[nums[i]] = nums[i]` ： 代表 索引 `nums[i]` 处和 索引 `i` 处的元素值都为 `nums[i]` ，即找到一组重复值，返回此值 `nums[i]` ；
    3.  否则： 交换索引为 `i` 和 `nums[i]` 的元素值，将此数字交换至对应索引位置。
2.  若遍历完毕尚未返回，则返回 `-1` 。

复杂度分析：

*  时间复杂度  O ( N ) O(N) O(N) ： 遍历数组使用  O ( N ) O(N) O(N) ，每轮遍历的判断和交换操作使用  O ( 1 ) O(1) O(1) 。
 *  空间复杂度  O ( 1 ) O(1) O(1)： 使用常数复杂度的额外空间。

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
            int i = 0;
            while(i < nums.length) {
        
                if(nums[i] == i) {
        
                    i++;
                    continue;
                }
                if(nums[i] == nums[nums[i]]) return nums[i];
                // 交换索引为i 和 nums[i] 的值
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
            return -1;
        }
    }

[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/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221022/5937d6d16f834a8d96e97596b89cb68f.png