Skip to content

961. N-Repeated Element in Size 2N Array

Description

You are given an integer array nums with the following properties:

  • nums.length == 2 * n.
  • nums contains n + 1 unique elements.
  • Exactly one element of nums is repeated n times.

Return the element that is repeated n times.

 

Example 1:

Input: nums = [1,2,3,3]
Output: 3

Example 2:

Input: nums = [2,1,2,5,3,2]
Output: 2

Example 3:

Input: nums = [5,1,5,2,5,3,5,4]
Output: 5

 

Constraints:

  • 2 <= n <= 5000
  • nums.length == 2 * n
  • 0 <= nums[i] <= 104
  • nums contains n + 1 unique elements and one of them is repeated exactly n times.

Solutions

Solution 1

1
2
3
4
5
6
7
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        s = set()
        for x in nums:
            if x in s:
                return x
            s.add(x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> s = new HashSet<>(nums.length / 2 + 1);
        for (int i = 0;; ++i) {
            if (!s.add(nums[i])) {
                return nums[i];
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0;; ++i) {
            if (s.count(nums[i])) {
                return nums[i];
            }
            s.insert(nums[i]);
        }
    }
};

1
2
3
4
5
6
7
8
9
func repeatedNTimes(nums []int) int {
    s := map[int]bool{}
    for i := 0; ; i++ {
        if s[nums[i]] {
            return nums[i]
        }
        s[nums[i]] = true
    }
}

1
2
3
4
5
6
7
8
9
function repeatedNTimes(nums: number[]): number {
    const s: Set<number> = new Set();
    for (const x of nums) {
        if (s.has(x)) {
            return x;
        }
        s.add(x);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
    const s = new Set();
    for (const x of nums) {
        if (s.has(x)) {
            return x;
        }
        s.add(x);
    }
};

Comments