https://leetcode.com/problems/n-repeated-element-in-size-2n-array/
HashSet or repeated number stay within distance 2 or random 4 times
https://leetcode.com/articles/n-repeated-element-in-size-2n-array/
https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208317/C%2B%2B-2-lines-O(4)-or-O-(1)
https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208563/JavaC%2B%2BPython-O(1)-Solution
int repeatedNTimes(vector<int>& A) {
int n = A.size();
for (int i = 0; i < n; i += 2)
if (A[i] == A[i + 1])
return A[i];
if (A[0] == A[2] || A[0] == A[3])
return A[0];
return A[1];
}
https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208333/Circular-array-O(n)-time-and-O(1)-Space
https://jinx19.github.io/2018/12/23/LeetCode-Solution-2018-12-23-LeetCode-Solution-961-N-Repeated-Element-in-Size-2N-Array%E2%80%9C/
X. https://zhanghuimeng.github.io/post/leetcode-961-n-repeated-element-in-size-2n-array/
In a array
A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.
Return the element repeated
N times.
Example 1:
Input: [1,2,3,3] Output: 3
Example 2:
Input: [2,1,2,5,3,2] Output: 2
Example 3:
Input: [5,1,5,2,5,3,5,4] Output: 5
Note:
4 <= A.length <= 100000 <= A[i] < 10000A.lengthis even
HashSet or repeated number stay within distance 2 or random 4 times
https://leetcode.com/articles/n-repeated-element-in-size-2n-array/
If we ever find a repeated element, it must be the answer. Let's call this answer the major element.
Consider all subarrays of length 4. There must be a major element in at least one such subarray.
This is because either:
- There is a major element in a length 2 subarray, or;
- Every length 2 subarray has exactly 1 major element, which means that a length 4 subarray that begins at a major element will have 2 major elements.
Thus, we only have to compare elements with their neighbors that are distance 1, 2, or 3 away.
public int repeatedNTimes(int[] A) {
for (int k = 1; k <= 3; ++k)
for (int i = 0; i < A.length - k; ++i)
if (A[i] == A[i + k])
return A[i];
throw null;
}
https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208317/C%2B%2B-2-lines-O(4)-or-O-(1)
The intuition here is that the repeated numbers have to appear either next to each other (
A[i] == A[i + 1]), or alternated (A[i] == A[i + 2]).
The only exception is sequences like
[2, 1, 3, 2]. In this case, the result is the last number, so we just return it in the end. This solution has O(n) runtime.int repeatedNTimes(vector<int>& A) {
for (auto i = 0; i < A.size() - 2; ++i)
if (A[i] == A[i + 1] || A[i] == A[i + 2]) return A[i];
return A[A.size() - 1];
}
Another interesting approach is to use randomization (courtesy of @lee215 ). If you pick two numbers randomly, there is a 25% chance you bump into the repeated number. So, in average, we will find the answer in 4 attempts, thus O(4) runtime.
int repeatedNTimes(vector<int>& A, int i = 0, int j = 0) {
while (A[i = rand() % A.size()] != A[j = rand() % A.size()] || i == j);
return A[i];
}https://leetcode.com/problems/n-repeated-element-in-size-2n-array/discuss/208563/JavaC%2B%2BPython-O(1)-Solution
Check if
If so, we return
If not, it must be
where we miss the check between
A[i] == A[i - 1] or A[i] == A[i - 2]If so, we return
A[i]If not, it must be
[x, x, y, z] or [x, y, z, x]where we miss the check between
A[0] and A[1]O(N) time O(1) space public int repeatedNTimes(int[] A) {
for (int i = 2; i < A.length; ++i)
if (A[i] == A[i - 1] || A[i] == A[i - 2])
return A[i];
return A[0];
}int repeatedNTimes(vector<int>& A) {
int n = A.size();
for (int i = 0; i < n; i += 2)
if (A[i] == A[i + 1])
return A[i];
if (A[0] == A[2] || A[0] == A[3])
return A[0];
return A[1];
}
If a number is repeated N times in a list of size 2N, it is always possible for the repeated number to stay within a distance of 2.
Consider this exaple where N = 4, Number x is repeated twice. All possible comibnations for x to fit in a list of size 4 are:
[a,b,x,x]
[x,a,b,x] (distance between both the x is still 1, consider it as a circular list)
[x,a,x,b]
[x,x,a,b]
[a,x,b,x]
[a,x,x,b]
Consider this exaple where N = 4, Number x is repeated twice. All possible comibnations for x to fit in a list of size 4 are:
[a,b,x,x]
[x,a,b,x] (distance between both the x is still 1, consider it as a circular list)
[x,a,x,b]
[x,x,a,b]
[a,x,b,x]
[a,x,x,b]
class Solution:
def repeatedNTimes(self, A):
for i in range(len(A)):
if A[i - 1] == A[i] or A[i - 2] == A[i]:
return A[i]https://jinx19.github.io/2018/12/23/LeetCode-Solution-2018-12-23-LeetCode-Solution-961-N-Repeated-Element-in-Size-2N-Array%E2%80%9C/
另外，如果一个数字在一个2N数组中重复N次，那么必然存在，它后面一个数字或者它后面的后面一个数字和它相同,即总存在距离小于2的两个重复数字。
注意 x _ _ x 这种距离为1.
比如一个8长度为8的数组，假设 不符合这种条 件，假设距离都为3：
[x_ _ x_ _x _ _x_ _]
那么可见还需要插入的数字是 4 * 2 = 8,显然不 符合题意。
X. random
Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.
Time complexity: O(1) expected 4
Space complexity: O(1)
Space complexity: O(1)
int repeatedNTimes(vector<int>& A) {
int i = 0;
int j = 0;
while (i == j || A[i] != A[j]) {
i = rand() % A.size();
j = rand() % A.size();
}
return A[i];
}
感觉还是写得有点复杂。不需要用这么多判断。
int repeatedNTimes(vector<int>& A) { for (int i = 0; i < A.size() - 3; i++) { if (A[i] == A[i+1] || A[i] == A[i+2] || A[i] == A[i+3]) return A[i]; if (A[i+1] == A[i+2] || A[i+1] == A[i+3]) return A[i+1]; if (A[i+2] == A[i+3]) return A[i+2]; } return -1; }
public int repeatedNTimes(int[] A) {
Map<Integer, Integer> count = new HashMap();
for (int x : A) {
count.put(x, count.getOrDefault(x, 0) + 1);
}
for (int k : count.keySet())
if (count.get(k) > 1)
return k;
throw null;
}
