在长度2N的数组中找出重复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]

C

int repeatedNTimes(int* nums, int numsSize) { srand(time(NULL)); while (true) { int x = random() % numsSize, y = random() % numsSize; if (x != y && nums[x] == nums[y]) { return nums[x]; } } }

复杂度分析

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