《剑指offer刷题笔记》 1、找出数组中重复的数字【c++详细题解】

布满荆棘的人生 2021-07-24 19:23 339阅读 0赞

### **题目：** ###

给定一个长度为 `n`的整数数组 `nums`，数组中所有的数字都在`0∼n−1` 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

**注意**：如果某些数字不在 `0∼n−1` 的范围内，或数组中不包含重复数字，则返回 `-1`；

**样例：**

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
    
    返回 2 或 3。

### **思路1：** ###

时间复杂度 O ( n ) O(n) O(n)

使用`unordered_set`

### **c++代码1：** ###

class Solution { 
    public:
        int duplicateInArray(vector<int>& nums) { 
            unordered_set<int> hash; //set数组,不可以存贮重复元素
            int n =  nums.size();
            if(n==0) return -1;
            for(int i = 0; i < n; i++)
            { 
                if(nums[i] < 0||nums[i] > n-1)
                   return -1;
            }
            
            for(int i = 0; i < n; i++)
            { 
                if(hash.count(nums[i])!=0) //如果
                   return nums[i];
                else
                   hash.insert(nums[i]);
            }
            return -1;  //没有重复的数字，返回-1
        }
    };

### **思路2：** ###

(数组遍历)  O ( n ) O(n) O(n)  
首先遍历一遍数组，如果存在某个数不在0到n-1的范围内，则返回-1。

下面的算法的主要思想是把每个数放到对应的位置上，即让`nums[i] = i`。

从前往后遍历数组中的所有数，假设当前遍历到的数是 `nums[i]=x`，那么：

如果`x != i && nums[x] == x`，则说明 `x` 出现了多次，直接返回`x`即可；如果`nums[x] != x`那我们就把 `x`交换到正确的位置上，即 `swap(nums[x], nums[i])`，交换完之后如果`nums[i] != i`，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以`swap`操作最多会进行 `n` 次，不会发生死循环。  
循环结束后，如果没有找到任何重复的数，则返回`-1`。

时间复杂度分析  
每次`swap`操作都会将一个数放在正确的位置上，最后一次`swap`会将两个数同时放到正确位置上，一共只有 `n` 个数和 `n` 个位置，所以`swap`最多会进行 `n−1`次。所以总时间复杂度是  O ( n ) O(n) O(n)。

### **c++代码2：** ###

class Solution { 
    public:
        int duplicateInArray(vector<int>& nums) { 
            int n = nums.size();
            for (auto x : nums)
                if (x < 0 || x >= n)
                    return -1;
            for (int i = 0; i < n; i ++ ) { 
                while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
                if (nums[i] != i) return nums[i];
            }
            return -1;
        }
    };