题解 | #数组中重复的数字#

数组中重复的数字

http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524

题目的主要信息:
  • 一个长度为nn的数组中只有0到n1n-1的数字
  • 需要找出其中任意一个重复出现的数字
举一反三:

学习完本题的思路你可以解决如下题目:

JZ56. 数组中只出现一次的两个数字

JZ50. 第一个只出现一次的字符

JZ75. 字符流中第一个不重复的字符

方法一:位置重排(推荐使用)

思路:

既然数组长度为nn只包含了0到n1n-1的数字,那么如果数字没有重复,这些数字排序后将会与其下标一一对应。那我们就可以考虑遍历数组,每次检查数字与下标是不是一致的,一致的说明它在属于它的位置上,不一致我们就将其交换到该数字作为下标的位置上,如果交换过程中,那个位置已经出现了等于它下标的数字,那肯定就重复了。

具体做法:

  • step 1:遍历数组,遇到数组元素与下标相同的不用管。
  • step 2:遇到数组元素与下标不同,就将其交换到属于它的位置,交换前检查那个位置是否有相同的元素,若有则重复。
  • step 3:遍历结束完全交换也没重复,则返回-1.

图示:

alt

Java实现代码:

import java.util.*;
public class Solution {
    //交换函数
    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }
    public int duplicate (int[] numbers) {
        for(int i = 0; i < numbers.length; i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对,需要换到自己对应的位置
            else{
                //对应位置相等,重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers, i, numbers[i]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
}

C++实现代码:

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        for(int i = 0; i < numbers.size(); i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对,需要换到自己对应的位置
            else{
                //对应位置相等,重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers[i], numbers[numbers[i]]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
};

Python实现代码:

class Solution:
    #交换函数
    def swap(self, numbers: List[int], a: int, b: int):
        temp = numbers[a]
        numbers[a] = numbers[b]
        numbers[b] = temp
    
    def duplicate(self , numbers: List[int]) -> int:
        for i in range(len(numbers)):
            #该位置本来就是对的
            if numbers[i] == i:
                continue
            #位置不对,需要换到自己对应的位置
            else:
                #对应位置相等,重复
                if numbers[i] == numbers[numbers[i]]:
                    return numbers[i]
                #交换位置
                else:
                    self.swap(numbers, i, numbers[i])
                    i -= 1
        #没有重复
        return -1

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为数组长度,遍历一次数组,所有的交换都是O(1)O(1)
  • 空间复杂度:O(1)O(1),常数级变量,无额外辅助空间
方法二:哈希表(扩展思路)

知识点:哈希表

哈希表是一种根据关键码(key)直接访问值(value)的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)O(1)时间内得到value,因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路:

既然是找重复的问题,那我们利用哈希表记录频率也是一样可以的。只要遇到的元素在哈希表中出现过,它就重复了。

具体做法:

  • step 1:遍历数组,将没有出现过的元素加入哈希表。
  • step 2:遇到的元素在哈希表中出现过就是重复数组。
  • step 3:遍历结束也没找到就返回-1.

Java实现代码:

import java.util.*;
public class Solution {
    public int duplicate (int[] numbers) {
        //哈希表记录重复
        HashMap<Integer, Integer> mp = new HashMap<>();
        //遍历数组
        for(int i = 0; i < numbers.length; i++){
            //如果没有出现过就加入哈希表
            if(!mp.containsKey(numbers[i]))
                mp.put(numbers[i], 1);
            //否则就是重复数字
            else
                return numbers[i];
        }
        //没有重复
        return -1;
    }
}

C++实现代码:

class Solution {
public:
    int duplicate(vector<int>& numbers) {
        //哈希表记录重复
        unordered_map<int, int> mp;
        //遍历数组
        for(int i = 0; i < numbers.size(); i++){
            //如果没有出现过就加入哈希表
            if(mp.find(numbers[i]) == mp.end())
                mp[numbers[i]]++;
            //否则就是重复数字
            else
                return numbers[i];
        }
        //没有重复
        return -1;
    }
};

Python实现代码:

class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        #哈希表记录重复
        mp = dict()
        #遍历数组
        for num in numbers:
            #如果没有出现过就加入哈希表
            if num not in mp:
                mp[num] = 1
            #否则就是重复数字
            else:
                return num
        #没有重复
        return -1

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为数组长度,遍历一次数组,哈希表每次操作都是O(1)O(1)
  • 空间复杂度:O(n)O(n),哈希表最大的空间为数组长度
全部评论
python 版本末尾改一下 if numbers==[]: return -1 elif (not numbers[0]==0 ): return numbers[0] return -1
1 回复 分享
发布于 2022-05-09 13:24
楼主,你方法一的解法是错的,如果我输入的是[2,1,1,3,4,5],返回值为-1,并没有找出重复的数字。因为在做交换的时候,交换后的是有可能就是重复数字,但是i++,校验就被忽略了
9 回复 分享
发布于 2022-04-26 16:57
就这还是官方精华解题吗
2 回复 分享
发布于 2022-06-06 13:01
改成 while 循环遍历,当i == numbers[i]的时候才i++
点赞 回复 分享
发布于 2022-09-27 13:30 广东
方法一,位置重排,java实现的代码有误,反例如下:用数组{1,2,3,5,4,6,1,2,7}测试,输出结果是-1,但此数组却是有重复元素的,应该输出1或2. 改正方法为,在swap方法执行完的下移行 加上 i--; 即可. //交换完,应该先让i--,然后执行for循环中的i++,这样保持i不变,继续检查此处的索引和元素值是否相等 ​ //直到索引与元素值相等时,才能直接i++检查下一索引元素 ​//因为交换完只能保证从当前索引交换出去的值与那个索引相等,而当前索引交换来的新值不一定与当前索引相等 ​//因此得继续在当前索引下进行检查 ​
点赞 回复 分享
发布于 2022-09-13 14:12 天津
做交换的时候,交换后的是有可能就是重复数字问题 public int duplicate(int[] nums) { if (nums == null || nums.length <= 0) { return -1; } for (int i = 0; i < nums.length; i++) { // nums[i] != i 为了防止 做交换的时候,交换后的是有可能就是重复数字,之后i++,校验就被忽略了 while (nums[i] != i) { int t = nums[i]; if (t == nums[t]) { return t; } //交换 nums[i]和 nums[nums[i]](交换 t 和 nums[t]) int temp = t; t = nums[temp]; nums[temp] = temp; } } return -1; }
点赞 回复 分享
发布于 2022-09-05 20:30 上海
第一种方***导致数据越界了吧:比如[1000,100,100],只有3个元素,根据numbers[numbers[i]] 哪里有超过3个元素的下标
点赞 回复 分享
发布于 2022-08-30 09:05 广东
第一种方法有问题。numbers[numbers[i] 这块没有指定的长度也会抛出数组越界
点赞 回复 分享
发布于 2022-08-18 10:58 广东
第一种方法存在问题,由于并没有进行严格排序,无法保证实际numbers[i]=i,如测试向量为[2,3,1,0,1,5,0],输出为1
点赞 回复 分享
发布于 2022-08-01 15:06
小牛牛第一种方法不严谨了哦,我想着就有点问题,试了下果然不行,上面大佬也都指出来了
点赞 回复 分享
发布于 2022-05-23 22:03
1,2,2 也不对 , 在swap的时候把重复的数换到前面了,i++的时候,就遍历不到它了
点赞 回复 分享
发布于 2022-05-13 10:24
试了一下,确实如楼上所说,存在问题,我的想法是,不在排序中向前遍历,而是一直在一个下标出重复进行对比交换,直到该位置的数字对了为止,再进行i++,对下一个下标位置进行对比
点赞 回复 分享
发布于 2022-04-29 16:41

相关推荐

07-08 13:48
门头沟学院 C++
点赞 评论 收藏
分享
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
28
13
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务