随机选择法求重复N次的元素思路与算法

我们之间来看思路与算法：

我们可以每次随机选择两个不同的下标，判断它们对应的元素是否相等即可。如果相等，那么返回任意一个作为答案。

代码

C++

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n = nums.size();
        mt19937 gen{random_device{}()};
        uniform_int_distribution<int> dis(0, n - 1);

        while (true) {
            int x = dis(gen), y = dis(gen);
            if (x != y && nums[x] == nums[y]) {
                return nums[x];
            }
        }
    }
};

Java

class Solution {
    public int repeatedNTimes(int[] nums) {
        int n = nums.length;
        Random random = new Random();

        while (true) {
            int x = random.nextInt(n), y = random.nextInt(n);
            if (x != y && nums[x] == nums[y]) {
                return nums[x];
            }
        }
    }
}

C#

public class Solution {
    public int RepeatedNTimes(int[] nums) {
        int n = nums.Length;
        Random random = new Random();

        while (true) {
            int x = random.Next(n), y = random.Next(n);
            if (x != y && nums[x] == nums[y]) {
                return nums[x];
            }
        }
    }
}

Python3

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)

        while True:
            x, y = random.randrange(n), random.randrange(n)
            if x != y and nums[x] == nums[y]:
                return nums[x]

复杂度分析

• 时间复杂度：期望 O(1) 。选择两个相同元素的概率为 n/2n*(n-1)/2n≈1/4 ，因此期望 44 次结束循环。
• 空间复杂度：O(1) 。

今天的文章分享就到这里了，希望对大家的学习有帮助哦！