[Lc]面试题03数组中重复的数字

题目

题解

1. 排序法（改变输入数组）

数组排序后找重复项

• 时间复杂度$O(nlog{n})$，主要是排序花费的
• 空间复杂度$O(1)$

class Solution {//三种方法。1.排序
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = -1;
        for(int i=1; i<nums.size(); ++i){
            if(nums[i]==nums[i-1]){
                res = nums[i];
                break;
            }
        }
        return res;
    }
};

2. set法（不改变输入数组）

用set存值，遇到重复的返回

• 时间复杂度$O(n)$，遍历一遍
• 空间复杂度$O(n)$，set存值

class Solution {//三种方法。2.set
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_set<int> s;
        int res;
        for(auto n : nums){
            if(s.count(n)) res = n;
            s.insert(n);
        }
        return res;
    }
};

3. 挨个数字排序法（改变/不改变输入数组）

若无重复数字，则每个数字nums[i]和下标i相等

1. 挨个遍历数组，遇到i，判断nums[i]和i相不相等，若相等，遍历下一个
2. 若不相等，判断nums[i]与nums[nums[i]]相不相等，相等找到重复的数字，返回
3. 若不相等，交换两个数字，继续对i进行步骤1

• 时间复杂度$O(n)$，遍历一遍
• 空间复杂度
  1. 不使用额外数组$O(1)$,改变原输入数组
  2. 使用额外数组$O(n)$，不改变原输入数组

下面代码是改变输入数组的写法，不改变的比较简单，不写了

class Solution {//四个方法。3.挨个移动数字
public:
    int findRepeatNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for(int i=0; i<n; ++i){
            if(i == nums[i]) continue;
            if(nums[i] == nums[nums[i]]){
                res = nums[i];
                break;
            }else{
                swap(nums[i],nums[nums[i]]);
                i--;
            }
        }
        return res;
    }
};

4. 二分查找法

若没有重复数字，[0,n/2)的个数就等于n/2 1. 若大于n/2，说明左半边有重复数字，递归 2. 若小于n/2，说明右半边有重复数字，递归

- 时间复杂度$O(n)$，遍历一遍 - 空间复杂度$O(n)$，set存值

书上还写了一个二分查找法，然而我写了半天通过不了，用书上的源码也不行，看别人的题解的二分法也过不去，真是坑。如果有人通过了麻烦贴一下代码，谢谢