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
| int FindMostIds(vector<int> &ids)
{
map<int,int> hashIds;
map<int,int>::iterator it;
hashIds.clear();
for (int i = 0; i < ids.size(); i++)
{
it = hashIds.find(ids[i]);
if (hashIds.end() == it)
{
hashIds.insert(map<int,int>::value_type(ids[i],1));
}
else
{
it->second++;
}
}
int id = 0, count = -1;
for (it = hashIds.begin(); it != hashIds.end(); it++)
{
if (it->second > count)
{
id = it->first;
count = it->second;
}
}
return id;
}
|
This problem can be further optimized in two ways: 1) Optimize the solution itself; 2) If there are 3 “spammers,” each posting more than a quarter of all posts, how do we solve it? It’s late today, heading back to the dorm. I’ll solve it tomorrow – though I already have an idea.
Problem 1:
The book “Beauty of Programming” mentions that space complexity can be optimized to O(1).
After reading the book, here’s the hint:
Use one variable id to store the current ID and count to store the count of that ID, then compare for equality and maintain dynamically. The final id must be the spammer.
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
| int FindMostIds(vector<int> &ids)
{
if (ids.size() <= 0)
return -1;
int id = ids[0];
int count = 1;
for (vector<int>::size_type i = 1; i < ids.size(); i++)
{
if (0 == count)
{
id = ids[i];
count = 1;
continue;
}
if (id == ids[i])
{
count++;
}
else
{
count--;
}
}
return id;
}
|
Problem 2: This can be generalized from the approach in Problem 1, Solution 2: [my own idea, not rigorously tested, but the logic should be correct]
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
| void FindMostIds(vector<int> &ids)
{
if (ids.size() <= 0)
return ;
int id[3] = {-1, -1, -1};
int count[3] = {0, 0, 0};
for (vector<int>::size_type i = 1; i < ids.size(); i++)
{
bool flag = false;
for (int j = 0; j < 3; j++)
{
if (id[j] == ids[i])
{
count[j]++;
flag = true;
break;
}
}
if (flag) continue;
flag = false;
for (int j = 0; j < 3; j++)
{
if (count[j] == 0)
{
id[j] = ids[i];
count[j]++;
flag = true;
break;
}
}
if (flag) continue;
for (int j = 0; j < 3; j++)
{
count[j]--;
}
}
for (int i = 0; i < 3; i++)
{
cout << id[i] << '\t';
}
cout << endl;
}
|