|
4 | 4 | importjava.util.Iterator; |
5 | 5 | importjava.util.Set; |
6 | 6 |
|
7 | | -/**136. Single Number |
8 | | -
|
9 | | - Given a non-empty array of integers, every element appears twice except for one. Find that single one. |
10 | | -
|
11 | | - Note: |
12 | | - Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? |
13 | | -
|
14 | | - Example 1: |
15 | | - Input: [2,2,1] |
16 | | - Output: 1 |
17 | | -
|
18 | | - Example 2: |
19 | | - Input: [4,1,2,1,2] |
20 | | - Output: 4 |
21 | | -*/ |
22 | | - |
23 | 7 | publicclass_136 { |
24 | 8 |
|
25 | | -publicstaticclassSolution1 { |
26 | | -/** |
27 | | - * Approach 1: use set, since this problem explicitly states that every element appears twice |
28 | | - * and only one appears once so, we could safely remove the ones that are already in the set, |
29 | | - * O(n) time and O(n) space. HashTable approach works similarly like this one, but it could be |
30 | | - * more easily extend to follow-up questions. |
31 | | - */ |
32 | | -publicintsingleNumber(int[]nums) { |
33 | | -Set<Integer>set =newHashSet(); |
34 | | -for (inti :nums) { |
35 | | -if (!set.add(i)) { |
36 | | -set.remove(i); |
| 9 | +publicstaticclassSolution1 { |
| 10 | +/** |
| 11 | + * Approach 1: use set, since this problem explicitly states that every element appears twice |
| 12 | + * and only one appears once so, we could safely remove the ones that are already in the set, |
| 13 | + * O(n) time and O(n) space. HashTable approach works similarly like this one, but it could be |
| 14 | + * more easily extend to follow-up questions. |
| 15 | + */ |
| 16 | +publicintsingleNumber(int[]nums) { |
| 17 | +Set<Integer>set =newHashSet(); |
| 18 | +for (inti :nums) { |
| 19 | +if (!set.add(i)) { |
| 20 | +set.remove(i); |
| 21 | + } |
| 22 | + } |
| 23 | +returnset.iterator().next(); |
37 | 24 | } |
38 | | - } |
39 | | -returnset.iterator().next(); |
40 | 25 | } |
41 | | - } |
42 | 26 |
|
43 | | -publicstaticclassSolution2 { |
44 | | -/** |
45 | | - * Approach 2: bit manipulation, use exclusive or ^ to solve this problem: we're using the trick |
46 | | - * here: every number ^ itself will become zero, so, the only remaining element will be the one |
47 | | - * that appeared only once. |
48 | | - */ |
49 | | -publicintsingleNumber(int[]nums) { |
50 | | -intres =0; |
51 | | -for (inti :nums) { |
52 | | -res ^=i; |
53 | | - } |
54 | | -returnres; |
| 27 | +publicstaticclassSolution2 { |
| 28 | +/** |
| 29 | + * Approach 2: bit manipulation, use exclusive or ^ to solve this problem: we're using the trick |
| 30 | + * here: every number ^ itself will become zero, so, the only remaining element will be the one |
| 31 | + * that appeared only once. |
| 32 | + */ |
| 33 | +publicintsingleNumber(int[]nums) { |
| 34 | +intres =0; |
| 35 | +for (inti :nums) { |
| 36 | +res ^=i; |
| 37 | + } |
| 38 | +returnres; |
| 39 | + } |
55 | 40 | } |
56 | | - } |
57 | 41 | } |