【题目】

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.

【分析】

思路是计算数组前一半出现元素的频率，如果数目大于? n/2 ?就返回

【代码】

/*********************************
*   日期：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.

遇到不同的就相互抵销，遇到相同的就增加，当count = 0时，重新开始

【代码二】

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];
    }
};

[LeetCode]169.Majority Element