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<</span>int> &ids) { if (ids.size() <= 0) return ; int id[3] = {-1, -1, -1}; int count[3] = {0, 0, 0}; for (vector<</span>int>::size_type i = 1;i <</span> ids.size();i++) { bool flag = false; for (int j = 0;j <</span> 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 &lt;&lt;/span&gt; 3;j++) { if (count[j] == 0) { id[j] = ids[i]; count[j]++; flag = true; break; } } if (flag) continue; for (int j = 0;j &lt;&lt;/span&gt; 3;j++) { count[j]--; } } for (int i = 0;i &lt;&lt;/span&gt; 3;i++) { cout &lt;&lt; id[i] &lt;&lt; '\t' ; } cout &lt;&lt; endl; </code></pre> <p>}