-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path137.SingleNumberII.cpp
More file actions
85 lines (77 loc) · 2.05 KB
/
137.SingleNumberII.cpp
File metadata and controls
85 lines (77 loc) · 2.05 KB
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Tags: Bit Manipulation
*/
/* Method:
此处很巧妙的先对数组排序，把相同的元素放在相邻的位置。
也可以建立map统计每个元素出现的次数，但是这样空间复杂度变成o(n)。
*/
//Code:
//Code 1:
int singleNumber(vector<int>& nums) {
std::map<int, int> m;
for(auto&& num : nums)
{
if(m.find(num) != m.end())
++m[num];
else
m[num] = 1;
}
auto iter = std::find_if(m.begin(), m.end(),
[&](const std::pair<int, int>& p)
{return p.second != 3;});
return iter->first;
}
//Code 2:
class Solution {
public:
int singleNumber(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int i = 0, iEnd = nums.size();
while(i + 3 < iEnd)
{
if(nums[i] != nums[i + 2])
{
return nums[i];
}
else
{
i += 3;
}
}
return nums[i];
}
};
// Solution 2: count the number of bits
int singleNumber(std::vector<int>& nums)
{
int count[32] = {0};
int result = 0;
for (int i = 0; i < 32; ++i)
{
for (auto&& num : nums)
{
if ((num>>i) & 1)
count[i]++;
}
result |= (count[i]%3) << i;
}
return result;
}
// Solution 3: use bit manip
int singleNumber(std::vector<int>& nums)
{
int ones = 0, twos = 0, threes = 0;
for (auto&& num : nums)
{
twos |= ones & num; // bit occurs twice
ones ^= num; // bit occurs once
threes = ones & twos; // bit occurs three times
// clear the bit which occurs three times
ones &= ~threes;
twos &= ~threes;
}
return ones;
}