LeetCode : 169. Majority Element 众数

ゞ浴缸里的玫瑰 2021-06-24 16:11 455阅读 0赞

试题
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.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2
代码
随机加验证：

class Solution {
    public int majorityElement(int[] nums) {
        Random rand = new Random();
        int max = nums.length/2;
        while(true){
            int can = nums[rand.nextInt(nums.length)];
            if(valid(nums, can, max)){
                return can;
            }
        }    
    }
    public boolean valid(int[] nums, int can, int max){
        int count = 0;
        for(int n: nums){
            if(n==can) count++;
            if(count>max) return true;
        }
        return false;
    }
}

消除法：

class Solution {
    public int majorityElement(int[] nums) {
        int num=0,count=0;
        for(int n: nums){
            if(count==0){
                num = n;
                count++;
                continue;
            }
            if(n==num){
                count++;
            }else{
                count--;
            }
        }
        return num;
    }
}