LC题解-多数元素题解-摩尔投票法

原题

题解

• 排序，取中位数即为答案

• 使用摩尔投票法

摩尔投票法

    要获取的数据大于n/2，基于此理解。取一个数，与下一个数比较，如果想当则count+1，如果不等则count-1,等count等于0的时候，取下一个数继续该过程，最后留下的那个数一定是大于n/2的。

class Solution {
    public int majorityElement(int[] nums) {
        // 摩尔投票法思路

        int result = nums[0];
        int count = 1;

        for(int i = 1; i < nums.length; i++) {
            if(result == nums[i]){
                count++;
            } else {
                count--;
            }

            if(count == 0) {
                i++;
                if(i < nums.length){
                    result = nums[i];   
                    count = 1;
                }
            }
        }

        return result;
    }
}