[编程之美_2.3]寻找发帖“水王”

 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;
}

这个题1：可以继续优化；2：如果是出现3个发帖水王，每个人超过四分之一的帖子，该题如何解？今天晚了，先回宿舍，明日再解，其实我已经想到方法了。
问题1：
编程之美的书上说，可以在空间复杂度上优化到O(1)
看书之后得到提示：
用一个id来存当前id
count来存id的计数，然后比较是否相等，动态维护，最终的id一定是水王。

 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;
}

问题2：可以用问题1解法2的推广：[自己想的，没有经过严格测试，目测思想正确]

 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;
}