多种方法解数组中重复的数字

54 阅读 0 评论 36 点赞

我是靠谱客的博主热情未来，最近开发中收集的这篇文章主要介绍多种方法解数组中重复的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

多种方法解数组中重复的数字

文章目录

- 多种方法解数组中重复的数字
- - 题目描述：
  - 方法一：遍历(哈希表)
  - 方法二：排序
  - 方法三：原地置换
  - 方法四：枚举

题目描述：

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

方法一：遍历(哈希表)

首先，我先让大家介绍一下HashSet集合。

HashSet是Java集合Set的一个实现类，Set是一个接口，其实现类除HashSet之外，还有TreeSet，并继承了Collection，HashSet集合很常用，同时也是程序员面试时经常会被问到的知识点。

最重要的是，该容器中只能存储不重复的对象，这是我们这个方法最关键之处。

在这道题中，只需要找出数组中任意一个重复的数字即可，所以为了判断一个数字是否重复遇到，使用HashSet集合存储已经遇到的数字，如果遇到的一个数字已经在HashSet集合中，则当前的数字是重复数字。

具体步骤如下：

初始化集合为空集合，重复的数字 repeat = -1
遍历数组中的每个元素
将该元素加入集合中，判断是否添加成功。如果添加失败，说明该元素已经在集合中，因此该元素是重复元素，将该元素的值赋给 repeat，并结束遍历
返回 repeat

复杂性分析：

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

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

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        int n=nums.length;
        for (int i=0;i<n;i++) {
            int num=nums[i];
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

方法二：排序

将数组排序以后，再遍历一遍就知道哪个重复了。

但是，这个方法的时间复杂度是 O*(Nlog*N)，空间复杂度为O（1），同时也修改了原始数组。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            if(nums[i+1]==nums[i])
              return nums[i+1];
        }    
        return -1;  
    }
    }

方法三：原地置换

题目指出 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。

因此，可遍历数组并通过交换操作使元素的索引与值一一对应（即 nums[i] = i ）。因而，就能通过索引找到对应的值。

遍历中，当第二次遇到数字 x 时，一定有 nums[x] = x （因为第一次遇到 x 时已经将其交换至 nums[x] 处了）。利用以上方法，即可得到一组重复数字。

在这里插入图片描述

这个思路利用到了数组的元素值的范围恰好和数组的长度是一样的，因此数组本身可以当做哈希表来用。遍历一遍就可以找到重复值，但是修改了原始数组。

复杂度分析：

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

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
    for(int i = 0;i<nums.length;i++){
        while(nums[i] != i){
            if(nums[i] == nums[nums[i]]){
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
    }
}

方法四：枚举

最后这个方法极其暴力！

一维循环遍历数组中的每一个元素，二维循环判断该元素之前是否存在相等的值！

时间复杂度：O（N^2）

空间复杂度：O（1）

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] == nums[j]) 
                    return nums[i];
            }
        }
        return -1;
    }
}