首页 » 编程之美 » 正文

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

int FindMostIds(vector<</span>int> &ids)
{
    map<</span>int,int>hashIds;
    map<</span>int,int>::iterator it;
    hashIds.clear();
    for (int i = 0;i <</span> ids.size();i++)
    {
        it = hashIds.find(ids[i]);
        if (hashIds.end() == it)
        {
            hashIds.insert(map<</span>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一定是水王。

int FindMostIds(vector<</span>int> &ids)
{
    if (ids.size() <= 0)
        return -1;
    int id = ids[0];
    int count = 1;
    for (vector<</span>int>::size_type i = 1;i <</span> ids.size();i++)
    {
        if (0 == count)
        {
            id = ids[i];
            count = 1;
            continue;
        }
        if (id == ids[i])
        {
            count++;
        }
        else
        {
            count--;
        }
    }
    return id;
}

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

void FindMostIds(vector&lt;&lt;/span&gt;int&gt; &amp;ids)
{
    if (ids.size() &lt;= 0)
        return ;
    int id[3] = {-1, -1, -1};
    int count[3] = {0, 0, 0};
    for (vector&lt;&lt;/span&gt;int&gt;::size_type i = 1;i &lt;&lt;/span&gt; ids.size();i++)
    {
        bool flag = false;
        for (int j = 0;j &lt;&lt;/span&gt; 3;j++)
        {
            if (id[j] == ids[i])
            {
                count[j]++;
                flag = true;
                break;
            }
        }
        if  (flag) continue;</p>

<pre><code>    flag = false;
    for (int j = 0;j &amp;lt;&amp;lt;/span&amp;gt; 3;j++)
    {
        if (count[j] == 0)
        {
            id[j] = ids[i];
            count[j]++;
            flag = true;
            break;
        }
    }
    if (flag) continue;
    for (int j = 0;j &amp;lt;&amp;lt;/span&amp;gt; 3;j++)
    {
        count[j]--;
    }
}    
for (int i = 0;i &amp;lt;&amp;lt;/span&amp;gt; 3;i++)
{
    cout &amp;lt;&amp;lt; id[i] &amp;lt;&amp;lt; '\t' ;
}
cout &amp;lt;&amp;lt; endl;
</code></pre>

<p>}

发表评论