# [LeetCode]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.

#### 【代码】

/*********************************
*   日期：2015-01-30
*   作者：SJF0115
*   题目: 169.Majority Element
*   网址：https://oj.leetcode.com/problems/majority-element/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
int majorityElement(vector<int> &num){
int len = num.size();
int size = len / 2 + 1;
int count;
// 统计前一半的元素个数
for(int i = 0;i < size;++i){
// 跳过重复元素
while(i > 0 && num[i] == num[i-1]){
++i;
}//while
count = 0;
for(int j = i;j < len;++j){
if(num[j] == num[i]){
++count;
if(count >= (len+1)/2){
return num[i];
}//if
}//if
}//for
}//for
}
};

int main(){
Solution solution;
vector<int> num = {8,8,7,7,7};
int result = solution.majorityElement(num);
// 输出
cout<<result<<endl;
return 0;
}


#### 【分析二】

Every number in the vector votes for itself, the majority number gets the most votes. Different number offsets the votes.

#### 【代码二】

class Solution {
public:
int majorityElement(vector<int> &num){
int vote = num[0];
int count = 1;
int size = num.size();
//vote from the second number
for(int i = 1;i < size;++i){
if(count == 0){
vote = num[i];
count++;
}//if
else if(vote == num[i]){
count++;
}
else{
count--;
}
}//for
return vote;
}
};

#### 【分析】

Majority Element肯定占据至少一半的元素，因此排序后中间元素一定是Majority Element

#### 【代码】

class Solution {
public:
int majorityElement(vector<int> &num){
int size = num.size();
// 只有一个元素
if(size == 1){
return num[0];
}//if
sort(num.begin(),num.end());
return num[size / 2];
}
};

|
9月前
Leetcode 230. Kth Smallest Element in a BST

54 1
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix

86 0
|

LeetCode 229. Majority Element II

72 0
|

LeetCode 162. Find Peak Element

86 0
|

LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
78 0
LeetCode 215. Kth Largest Element in an Array

68 0
|
Java C++
LeetCode之Remove Element
LeetCode之Remove Element
94 0
LeetCode之Next Greater Element I
LeetCode之Next Greater Element I
70 0
|

LeetCode 169 Majority Element（主要元素）（vector、map）

793 0
|
6天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III

18 6