LeetCode (Others) Majority Element

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.

Example 1:

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

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

思路：暴力枚举是最容易想到的，但是肯定会超时，因为时间复杂度是o(n2)。仔细看题目：数组中出现次数超过一半的数，也就是说如果把这个数字抽出来组成一个新的数组的话，这个新的数组的长度是要大于原来数组长度的1/2的，所以我们能想到这样一个解法，利用排序，使得原数组中的所有数字有序后，位于数组中间位置的数肯定就是出现次数超过一半的数，因为所有的数都有序的话，这个出现次数超过一半的数的长度要大于原数组的一半，所以不管是在前半段还是在后半段，这个数字都必然会占据nums[leng/2]这个位置。有了这个思想以后，这道题就很简单了。

java代码如下：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}