题目描述

寻找出现的重复数

算法1

一次遍历 , 交换遍历到的数到它该去的地方

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0 ; i < n ; i++){
            if(nums[i] < 0 || nums[i] >= n) return -1;
            //当i没有出现了在nums[i]上的时候 , 就不断的交换数组中的两个位置
            while(i != nums[i] && nums[nums[i]] != nums[i]){
                swap(nums[i] , nums[nums[i]]);
            }
            //如果nums[i]没有出现在该出现的位置 , 但是正确的位置上却有了正确的数字 , 则nums[i]出现了两次
            if(nums[i]!=i && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }
};

算法2

哈希表 (这种方式可以找出所有的重复数)

C++ 代码

class Solution{
public : 
    int findRepeatNumber(vector<int>& nums){
        vector<int> res;
        //用来记录词频
        unordered_map<int , int> m;
        int i = 0 ;
        //遍历一次 , 把遍历到的数字的词频+1
        for(int i = 0 ; i< nums.size() ; i++){
            m[nums[i]]+=1;
            //词频>1 , 则res中可以添加-1 (这种方式可以找出所有)
            if(m[nums[i]] > 1 ) {
                res.push_back(nums[i]);
            }
        }
    }
    return res[i];
};

算法3

排序

C++ 代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        int i=1;
        sort(nums.begin() , nums.end());
        for(int i = 1 ; i < n ; i++){
            if(nums[i] == nums[i-1]){
                return nums[i];
            }
        }
        return nums[i];
    }
};

算法2(本质上还是哈希)

遍历到的数字词频+1

python(参考评论区的代码 , 只为了自己熟悉python)

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        #统计长度
        lenth = len(nums)
        #初始化一个res数组 ,全是0
        res = [0] * lenth
        #enumerate遍历nums
        #i是小标 , num是数字
        for i, num in enumerate(nums):
            #这个数字超过n 或者 小于0, 都是不合法的
            if num >= lenth or num < 0:
                #按照要求 不合法的返回-1;
                return -1
            #否则就是合法的 , 在res中的num位置的频率+1;
            res[num] += 1

        #再次enumerate遍历
        #只要遍历到的数字i , 频率>1 , 说明数字i出现了多次 , 返回i
        for i, num in enumerate(res):
            if num > 1:
                return i
        return -1