长大后想做什么？做回小孩！

0%

LeetCode——多数元素

发表于 更新于 分类于 Valine：
本文字数： 300

NO.169 多数元素 简单

8n497q.png

思路一：排序法 因为题目中说总是存在多数元素，这个多数元素的个数大于半数，所以无论是升序还是降序排序之后中间元素一定是多数元素。

1
2
3
4
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

时间复杂度：O(nlogn)

思路二：哈希表 遍历一遍统计不同数字出现次数，然后遍历哈希表找出多数元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int majorityElement(int[] nums) {
    //统计数字出现次数
    HashMap<Integer,Integer> map=new HashMap<>();
    for (int num : nums) {
        Integer value = map.getOrDefault(num, 0);
        map.put(num,value+1);
    }
    //遍历map，打擂台找到多数元素
    int ans=0,maxNum=0;
    for (Map.Entry<Integer, Integer> en : map.entrySet()) {
        if (en.getValue()>maxNum){
            ans=en.getKey();
            maxNum=en.getValue();
        }
    }
    return ans;
}

时间复杂度：O(n)

思路三：摩尔投票法 基于题目中说的多数元素一定存在。

简单说就是先定一个候选人和计数器count，然后遍历过程中遇到和候选人相同的就count+1，不同则count-1，当count==0，就更换当前元素为新的候选人并将count置为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
    int candidate=nums[0],count=0;
    for (int num : nums) {
        if (num==candidate){
            count++;
        }else {
            count--;
        }
        if (count==0){
            candidate=num;
            count=1;
        }
    }
    return candidate;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github