961 N-Repeated Element in Size 2N Array

Easy

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:

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

Example 2:

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

Example 3:

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

Note:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. A.length is even

想法

每次都把一个不难的题弄得很难,sigh

实际上就是用set查重,值得注意的是C++里set是用红黑树实现的。

最后就是Range-based for loop,C++11的新特性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>

int main() {
std::vector<int> v = {0, 1, 2, 3, 4, 5};

for (const int& i : v) // access by const reference
std::cout << i << ' ';
std::cout << '\n';

for (auto i : v) // access by value, the type of i is int
std::cout << i << ' ';
std::cout << '\n';

for (auto&& i : v) // access by forwarding reference, the type of i is int&
std::cout << i << ' ';
std::cout << '\n';

const auto& cv = v;

for (auto&& i : cv) // access by f-d reference, the type of i is const int&
std::cout << i << ' ';
std::cout << '\n';

for (int n : {0, 1, 2, 3, 4, 5}) // the initializer may be a braced-init-list
std::cout << n << ' ';
std::cout << '\n';

int a[] = {0, 1, 2, 3, 4, 5};
for (int n : a) // the initializer may be an array
std::cout << n << ' ';
std::cout << '\n';

for (int n : a)
std::cout << 1 << ' '; // the loop variable need not be used
std::cout << '\n';

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int repeatedNTimes(vector<int> &A)
{
set<int> m;
for (vector<int>::iterator it = A.begin(); it != A.end(); it++) {
if (m.find(*it) != m.end()) {
return *it;
}
else {
m.insert(*it);
}
}
}

不过有个更好的做法,在LeetCode上看到的:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
unordered_set<int> seen;
for (int a: A) {
if (seen.count(a))
return a;
seen.insert(a);
}
return 0;
}
};

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×