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: Hash Table

Since the array \(\textit{nums}\) has a total of \(2n\) elements, with \(n + 1\) distinct elements, and one element repeated \(n\) times, this means the remaining \(n\) elements in the array are all distinct.

Therefore, we only need to iterate through the array \(\textit{nums}\) and use a hash table \(s\) to record the elements we've encountered. When we encounter an element \(x\), if \(x\) already exists in the hash table \(s\), it means \(x\) is the repeated element, and we can directly return \(x\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(\textit{nums}\).

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);
    }
};

Solution 2: Mathematics

According to the problem description, half of the elements in the array \(\textit{nums}\) are the same. If we view the array as a circular arrangement, then there is at most \(1\) other element between two identical elements.

Therefore, we iterate through the array \(\textit{nums}\) starting from index \(2\). For each index \(i\), we compare \(\textit{nums}[i]\) with \(\textit{nums}[i - 1]\) and \(\textit{nums}[i - 2]\). If they are equal, we return that value.

If we don't find the repeated element in the above process, then the repeated element must be \(\textit{nums}[0]\), and we can directly return \(\textit{nums}[0]\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        for i in range(2, len(nums)):
            if nums[i] == nums[i - 1] or nums[i] == nums[i - 2]:
                return nums[i]
        return nums[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int i = 2; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) {
                return nums[i];
            }
        }
        return nums[0];
    }
}

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

1
2
3
4
5
6
7
8
func repeatedNTimes(nums []int) int {
    for i := 2; i < len(nums); i++ {
        if nums[i] == nums[i-1] || nums[i] == nums[i-2] {
            return nums[i]
        }
    }
    return nums[0]
}

1
2
3
4
5
6
7
8
function repeatedNTimes(nums: number[]): number {
    for (let i = 2; i < nums.length; ++i) {
        if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) {
            return nums[i];
        }
    }
    return nums[0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
    for (let i = 2; i < nums.length; ++i) {
        if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) {
            return nums[i];
        }
    }
    return nums[0];
};

Comments