961. N-Repeated Element in Size 2N Array

2023, Mar 08 2 mins read

1. 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.

2. Example

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

3. 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.

4. Solutions

Math

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// betwwen two repeated number, we have at most one unique number when n > 2
// when n == 2, we have at most two unique numbers
// because n + 2(n - 1) > 2n
// so we just need to check 3 continous numbers and front/back
class Solution {
public:
    int repeatedNTimes(vector<int> &nums) {
        if (nums.front() == nums.back()) {
            return nums.front();
        }

        for (int i = 1; i < nums.size() - 1; ++i) {
            if (nums[i - 1] == nums[i] || nums[i - 1] == nums[i + 1]) {
                return nums[i - 1];
            } else if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }

        return -1;
    }
};

Search

Tags