169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

---

做题思路

• 本题我是想到了两个方法

• 第一个方法读完题目就想到了：Map

  需要注意的是Map的一些API我们要熟记，否则这里你虽然知道要使用哪个API但是你的名字

  可能会拼写错误

  map.put()

  map.put(num,map.getOrDefault(num,0)+1);

  Map.Entry

  map.entrySet()

  Entry.getKey()

  Entry,getValue()

• 第二个方法也很巧妙，需要我们稍微的思考一下~

  定义初始一个count=1 key=nums[0]

  通过循环遍历数组从下标1开始，如果nums[i]==key 那么就让count+1 紧接着判断是否满足

  count>n/2

  如果nums[i]!=key count-- 在判断if(count==0){ key=nums[i]; count=1 }

代码实现

//法1
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int res=0;
        int k=nums.length>>1;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()>k){
                res=entry.getKey();
                break;
            }
        }
        return res;
    }
}

//法2

class Solution {
    public int majorityElement(int[] nums) {
        int key=nums[0];
        int count=1;
        int c=nums.length>>1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==key){
                count++;
                if(count>c)break;
            }else{
                count--;
                if(count==0){
                    key=nums[i];
                    count=1;
                }
            }
        }
        return key;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

题目链接

169. 多数元素