961. N-Repeated Element in Size 2N Array
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)
// 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;
}
};