在长度2N的数组中找出重复N次的元素（四）

方法三随机选择思路与算法我们可以每次随机选择两个不同的下标判断它们对应的元素是否相等即可。如果相等那么返回任意一个作为答案。代码Cclass Solution { public: int repeatedNTimes(vectorint nums) { int n nums.size(); mt19937 gen{random_device{}()}; uniform_int_distributionint dis(0, n - 1); while (true) { int x dis(gen), y dis(gen); if (x ! y nums[x] nums[y]) { return nums[x]; } } } };Javaclass 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]; } } } }Python3class 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]Cint 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) 。