用了排序跟抵消。

题目

由题可知，多数元素是指在数组中出现次数大于一半的元素，且总是存在多数元素。不难想到，把数组排序后，这个数组的中间数一定是这个要找的元素。

用了sort排序，时间复杂度O（nlogn），空间复杂度O（1）。

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

然后，也可以用抵消的思路，类似投票候选人，记要找的元素为1，其它元素为-1，这样累加下来肯定是为1的，然后就是通过前面几个数作抵消，当剩余那个数即找到候选人，也是要找的元素了。

时间复杂度O（n），空间复杂度O（1），相对更快一点。

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

一题多解，转变思路很重要。