【Leetcode】 169. Majority Element

Description

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else {
            return nums[len / 2];
        }
    }

Optimization

public int majorityElement(int[] nums) {
        int count = 1;
        int major = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                major = nums[i];
                count = 1;
            } else if (major == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return major;
    }

Analyse

这里注意是大于长度的一半的，所以可以根据条件来加count。