力扣 多数元素

用了排序跟抵消。

题目

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

用了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;}  
}

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