首页 > 代码库 > LeetCode Problem: Majority Element查找多数元素
LeetCode Problem: 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：Moore voting algorithm--每找出两个不同的element，就成对删除即count--，最终剩下的一定就是所求的。时间复杂度：O(n)
1 class Solution { 2 public: 3 int majorityElement(vector<int> &num) { 4 5 int elem = 0; 6 int count = 0; 7 8 for(int i = 0; i < num.size(); i++) { 9 10 if(count == 0) {11 elem = num[i];12 count = 1;13 }14 else {15 if(elem == num[i])16 count++;17 else18 count--;19 }20 21 }22 return elem;23 }
};
思路2：随机挑选一个元素，检查是否是多数元素。时间复杂度：Average：O(n)。期望查找次数 <2
1 class Solution { 2 public: 3 int majorityElement(vector<int> &num) { 4 5 int count = 0; 6 7 for(;;) { 8 if(num.size() == 1) 9 return num[0];10 else {11 int i = rand() % (num.size() - 1);12 for(int j = 0; j < num.size(); j++) {13 if(num[j] == num[i])14 count++;15 }16 if(count > (num.size() / 2))17 return num[i];18 else {19 count = 0;20 continue;21 }22 }23 }24 }
};
附LeetCode建议解决方案：
LeetCode Problem: Majority Element查找多数元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。