LeetCode169 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. 如果一个数组里某个元素出现的次数超过总数的一半，那么，就把这个元素称为优先元素，找到这个元素。

解题思路

看到题目的第一想法是遍历，读取每个元素出现的次数，然后选取出现次数最多的那个。然后想想，这样的话优先元素超过总数一半的条件不就没什么用，如果把整个数组排个序，在有序条件下某个元素出现次数超过一半，那么中位数不就是优先元素吗。 想通了思路，编码就很简单。

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