[leetcode] 169. Majority Element解題レポート

タイトルリンク:https://leetcode.com/problems/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. 考え方:本題には2つの方法があります.
1.高速ソートの分割アルゴリズムに基づいて、partition関数は毎回配列を2つの部分に分け、1つの値を正しい位置に並べ、この位置がn/2であれば、この数は必ずn/2回を超える数であることを示す.この方法はK番目に大きい数を探すことも同様に処理できる.
コードは次のとおりです.

class Solution {
public:
    int partition(vector<int>& nums, int begin, int end){
        int value = nums[begin];
        while(begin < end){
            while(begin < end && value < nums[end])
                end--;
            if(begin < end)
                nums[begin++] = nums[end];
            while(begin < end && value > nums[begin])
                begin++;
            if(begin < end)
                nums[end--] = nums[begin];
        }
        nums[begin] = value;
        return begin;
    }
    int majorityElement(vector<int>& nums) {
        int start = 0;
        int end = nums.size() -1;
        int index = partition(nums, start, end);
        while(index != (nums.size()/2)){
            if(index > nums.size()/2){
                end = index - 1;
                index = partition(nums, start, end);
            }
            else if(index < nums.size()/2){
                start = index + 1;
                index = partition(nums, start, end);
            }
        }
        return nums[nums.size()/2];
    }
};

２. もう1つはBM投票アルゴリズムで、カウンタを設定し、カウンタが0であれば現在数の個数を統計し、そうでなければ現在数が統計する数に等しい場合はカウンタに1を加算し、そうでなければ1を減算する.
コードは次のとおりです.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0, num, len = nums.size();
        for(int i =0; i< nums.size(); i++)
        {
            if(cnt == 0) num = nums[i];
            cnt = (num == nums[i])?(cnt+1):(cnt-1);
        }
        return num;
    }
};