169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than n/2
times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路1:
使用map来处理。
class Solution { public: int majorityElement(vector<int>& nums) { map<int, int> record; for (int i = 0; i < nums.size(); i++) { if (record.find(nums[i]) == record.end()) { record.insert(pair<int, int>(nums[i], 1)); if (record[nums[i]] > nums.size() / 2) { return nums[i]; } } else { record[nums[i]] += 1; if (record[nums[i]] > nums.size() / 2) { return nums[i]; } } } return 0; } };
思路2:
采用双循环
int majorityElement(vector<int>& nums) { int hit = 0; int currentElem; for (int i = 0; i < nums.size(); i++) { currentElem = nums[i]; hit = 0; for (int j = 0; j < nums.size(); j++) { if (nums[j] == currentElem) { hit++; if (hit > nums.size() / 2) { return currentElem; } } } } return 0; }
2016-08-10 12:19:37
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。