LeetCode 961.在长度2N的数组中找出重复N次的元素 - 【LetMeFly】四种方式解决

力扣题目链接：https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/

给你一个整数数组 n u m s nums nums ，该数组具有以下属性：

• n u m s . l e n g t h = = 2 ∗ n nums.length == 2 * n nums.length==2∗n.
• n u m s nums nums 包含 n + 1 n + 1 n+1 个 不同的 元素
• n u m s nums nums 中恰有一个元素重复 n n n 次

找出并返回重复了 n n n 次的那个元素。

示例 1:

输入：nums = [1,2,3,3]
输出：3

示例 2:

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3:

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

提示:

• 2 ≤ n ≤ 5000 2leq nleq 5000 2≤n≤5000
• n u m s . l e n g t h = = 2 ∗ n nums.length == 2 * n nums.length==2∗n
• 0 ≤ n u m s [ i ] ≤ 1 0 4 0leq nums[i]leq10^4 0≤nums[i]≤104
• n u m s nums nums由 n + 1 n+1 n+1个不同的元素组成，且其中一个元素恰好重复n次

有一个元素出现了 n n n次，其余元素都只出现了 1 1 1次

这让我们很容易想到排序。排序后相同的数字会挨到一起，从前向后遍历数组，如果有相邻的两个数字相同，那么这个数字就是答案。

• 时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度 O ( n ) O(n) O(n)

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;  // Fake return：LeetCode编译器必须要求有一个返回值
    }
};

我们可以用哈希表记录下每个数出现的次数，如果遇到出现两次的数字就是答案。

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

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        unordered_set appended;  // 记录已经出现过的元素
        for (int& t : nums) {  // 遍历
            if (appended.count(t)) {  // 出现过
                return t;
            }
            appended.insert(t);
        }
        return -1;  // Fake return
    }
};

首先我们可以思考：一个数组中有 n n n个相同的数，这些相同的数中，距离最近的两个数的最大距离是多少呢？

答案肯定不会很大吧。实际上确实如此。证明如下：

记 n n n个相同的数为 x x x，假设每两个 x x x之间都间隔了 ≥ 2 geq2 ≥2个数。那么 n n n个 x x x需要至少 2 × ( n − 1 ) 2times(n-1) 2×(n−1)个数来间隔。但是非 x x x的数只有 n n n个。只有 n ≥ 2 × ( n − 1 ) ngeq 2times(n-1) n≥2×(n−1)时上述假设才成立。解得 n ≤ 2 nleq2 n≤2。
也就是说，只有 n = 2 n=2 n=2时，才有可能满足两个 x x x之间间隔 ≥ 2 geq2 ≥2（ [ x , a , b , x ] [x,a,b,x] [x,a,b,x]）
n > 2 n>2 n>2时，必存在两个间距 < 2 <2 <2的相同的 x x x。

因此我们只需要在“相邻两个数、间隔一个数”的条件下，就能找到答案（ n = 2 n=2 n=2时除外）

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

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        if (nums.size() == 4) {  // n = 2时特判
            for (int i = 0; i < 4; i++) {
                for (int j = i + 1; j < 4; j++) {
                    if (nums[i] == nums[j]) {
                        return nums[i];
                    }
                }
            }
        }
        // n > 2
        for (int i = 0; i < nums.size(); i++) {
            if (i + 1 < nums.size() && nums[i + 1] == nums[i]) {
                return nums[i];
            }
            if (i + 2 < nums.size() && nums[i + 2] == nums[i]) {
                return nums[i];
            }
        }
        return -1;  // Fake return
    }
};

这种方法就是无脑随机选取两个下标不同的数，看两个数是否相等。如果不相等继续选择，直到相等为止。

这种方法看似很笨，其实效率很高。因为选择两个数相同的概率是 n 2 n × n − 1 2 n ≈ 1 4 frac{n}{2n}timesfrac{n-1}{2n}approx frac{1}{4} 2nn​×2nn−1​≈41​，平均 4 4 4次随机选择就能找到答案。因此期望时间复杂度为 O ( 1 ) O(1) O(1)。

• 期望时间复杂度 O ( 1 ) O(1) O(1)
• 空间复杂度 O ( 1 ) O(1) O(1)

// 不可以这样写，因为这样可能会选取两个相同的下标
class Solution {
public:
    int repeatedNTimes(vector& nums) {
        srand(time(NULL));
        int location;
        do {
            location = rand() % nums.size();
        } while (nums[location] != nums[rand() % nums.size()]);
        return nums[location];
    }
};

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        srand(time(NULL));
        int loc1, loc2;
        do {
            loc1 = rand() % nums.size();
            loc2 = rand() % nums.size();
        } while (nums[loc1] != nums[loc2]);
        return nums[loc1];
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124897591