参考:https://blog.nowcoder.net/n/a9df4dee431a4d6c9cf080ba06fa439d
方法一:哈希表
链接:https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion 来源:牛客网 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { unordered_map<int,int> mp; for (const int val : numbers) ++mp[val]; for (const int val : numbers) { if (mp[val] > numbers.size() / 2 ) return val; } return 0; } };
方法二:排序法:
链接:https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion 来源:牛客网 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { sort(numbers.begin(), numbers.end()); int cond = numbers[numbers.size() / 2]; int cnt = 0; for (const int k :numbers) { if (cond == k) ++cnt; } if (cnt > numbers.size() / 2) return cond; return 0; } };
方法三:候选法(最优解)
链接:https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion 来源:牛客网 class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int cond = -1; int cnt = 0; for (int i=0; i<numbers.size(); ++i) { if (cnt == 0) { cond = numbers[i]; ++cnt; } else { if (cond == numbers[i]) ++cnt; else --cnt; } } cnt = 0; for (const int k :numbers) { if (cond == k) ++cnt; } if (cnt > numbers.size() / 2) return cond; return 0; } };