LeetCode百题【多数元素】

题目描述

题目描述.png

解法一

哈希表
先将元素存入哈希表，后再对哈希表进行遍历
- 通过哈希表进行存储数据
- key为元素值
- value为出现的次数

class Solution {
    public int majorityElement(int[] nums) {
       int result=0;
       int cntMax=0;
       Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for (int num : nums) {
            if(!map.containsKey(num)){
                map.put(num,1);
            }
            else{
                map.put(num,map.get(num)+1);
            }
        }

        for (Integer integer : map.keySet()) {
            if(map.get(integer)>cntMax){
                cntMax=map.get(integer);
                result=integer;
            }
                
        }

        return result;
    }
    
}

时间复杂度

时间复杂度：O(n)其中 n 是数组 nums 的长度。我们遍历数组 nums 一次，对于 nums 中的每一个元素，将其插入哈希表都只需要常数时间。遍历哈希表的时间复杂度为O(1)

因此总时间复杂度为O(n)

解法二

摩尔投票法
- 简单来讲就是不同元素相互抵消，最后剩下的就是最多的元素

class Solution {
    public int majorityElement(int[] nums) {
       int result=nums[0];
       int cnt=1;
        for (int i = 1; i < nums.length; i++) {
            if(result==nums[i]){
                cnt++;
            }
            else {
                cnt--;
                if(cnt==0){
                    result=nums[i+1];
                }

            }
        }
        return result;
    }
}