今日简单题：https://leetcode-cn.com/problems/majority-element/
看到要统计每个数字出现的次数，第一反应仍然是for循环遍历数组，用HashMap，Key存数字，Value累计次数，当次数>n/2时，直接返回Key。
最暴力的方式也可以是整个数组遍历完，对次数做排序再返回，但是题目中有一个条件是，一定会存在众数，且众数出现的次数一定>n/2，这就意味着，一个数组里有且仅有一个众数。
本来想到这里就应该开始做题了，但是底下进阶要求时间复杂度O(n)，空间复杂度O(1)，这就意味着如果我们用HashMap来存放，空间复杂度一定不符合要求，所以还得再想想。
这个时候就想到了排序，排序后，不管是升降序，众数一定会至少在n/2附近结束，这个思路其实可以用滑动窗口来直观理解。
n/2坐标一定会是众数
排序法：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
网友评论