剑指 offer 面试题03. 数组中重复的数字

LeetCode 拿到了 <<剑指offer>> 的官方授权了哈哈厉害

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

示例 1：

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

限制：

2 <= n <= 100000

面试题03. 数组中重复的数字

Solution

C++

解法一: 使用 set 过滤, 或者 hash 过滤
优化效率: 有重复则提前返回

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        set<int> s;
        for (int i = 0;i<nums.size();i++) {
            if (s.count(nums[i])){
                return nums[i];
            }
            s.insert(nums[i]);
        }
        return -1;
    }
};

执行用时 :92 ms, 在所有 C++ 提交中击败了100.00%的用户 
内存消耗 :19.5 MB, 在所有 C++ 提交中击败了100.00%的用户
没多少提交用户 这击败比例没参考价值

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

解法二: 使用数组计数过滤, 原理类似 set 或者 hashtable

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

执行用时 :44 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :25 MB, 在所有 C++ 提交中击败了100.00%的用户

时间复杂度: O(n)
空间复杂度: O(n) ,算不算 O(1)呢, 按照题意限制了数组的长度与范围, 分配 100001个空间也是常数级别

解法三 : 类似桶排序, 进行数组原地排序, 因为题意限制了数组的长度是 n , 且数组的值范围在 0～n-1 .
那么我们将这个打乱顺序的数组, 按照下标和值对应的方式, 将数组排序. 多出来的值就是重复的值,
比较麻烦的处理是正确的做法是要保证交换的两个数字也同样对应对方的下标, 否则要递归一直交换下去.

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        if (nums.size() == 0) return -1;
        // 采用交换的思路, 不分配空间
        for (int i = 0;i<nums.size();i++) {
            int ret = placeRightPosition(nums,i,nums[i], nums[i],nums[nums[i]]);
            if (ret != -1){
                return ret;
            }
        }
        return -1;
    }
    
    int placeRightPosition(vector<int>& nums,int cur,int curValue, int next,int nextValue) {
        if (cur != next && curValue == nextValue) {
            return curValue;
        }
        
        nums[cur] = nextValue;
        nums[next] = curValue;
        if (nextValue == cur) {
            return -1;
        }
        int newNext = nextValue;
        int newNextValue = nums[nextValue];
        return placeRightPosition(nums,cur,nextValue,newNext,newNextValue);
    }
};

执行用时 :44 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :14 MB, 在所有 C++ 提交中击败了100.00%的用户

时间复杂度: O(n) 利用均摊的思路如果某一个索引递归次数多了, 你会发现其他索引基本不会执行递归了
空间复杂度: O(1) 尾递归

改成非递归的形式

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        if (nums.size() == 0) return -1;
        // 采用交换的思路, 不分配空间
        for (int i = 0;i< nums.size();i++) {
            while (i != nums[i]){
                int temp = nums[i];
                if (temp == nums[temp]) {
                    return temp;
                }
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
};

执行用时 :44 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :14.1 MB, 在所有 C++ 提交中击败了100.00%的用户

时间复杂度: O(n)
空间复杂度: O(1)

对我来说递归更容易写, 而且一般编译器会对一些递归进行优化, 其效率不一定比循环要低.