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

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

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

力扣题目链接: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==2n.
  • 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 2\leq n\leq 5000 2n5000
  • n u m s . l e n g t h = = 2 ∗ n nums.length == 2 * n nums.length==2n
  • 0 ≤ n u m s [ i ] ≤ 1 0 4 0\leq nums[i]\leq10^4 0nums[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(n\log n) O(nlogn)
  • 空间复杂度 O ( n ) O(n) O(n)
AC代码 C++
class Solution {
public:
    int repeatedNTimes(vector<int>& 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)
AC代码 C++
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> 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 ) 2\times(n-1) 2×(n1)个数来间隔。但是非 x x x的数只有 n n n个。只有 n ≥ 2 × ( n − 1 ) n\geq 2\times(n-1) n2×(n1)时上述假设才成立。解得 n ≤ 2 n\leq2 n2
也就是说,只有 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)
AC代码 C++
class Solution {
public:
    int repeatedNTimes(vector<int>& 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}\times\frac{n-1}{2n}\approx \frac{1}{4} 2nn×2nn141,平均 4 4 4次随机选择就能找到答案。因此期望时间复杂度为 O ( 1 ) O(1) O(1)

  • 期望时间复杂度 O ( 1 ) O(1) O(1)
  • 空间复杂度 O ( 1 ) O(1) O(1)
AC代码 C++错误示范
// 不可以这样写,因为这样可能会选取两个相同的下标
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        srand(time(NULL));
        int location;
        do {
            location = rand() % nums.size();
        } while (nums[location] != nums[rand() % nums.size()]);
        return nums[location];
    }
};
C++正确示范
class Solution {
public:
    int repeatedNTimes(vector<int>& 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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1295141.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存