LeetCode169. Majority Element解答

比眉伴天荒 2022-06-07 11:26 145阅读 0赞

天气冷了 ，有男朋友的抱男朋友，有女朋友的抱女朋友，而我就比较牛逼了

我不冷  
\#先来看一下题目

> Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

> You may assume that the array is non-empty and the majority element always exist in the array.  
> 题目大意是:给你一个长度为n的数组，要求你找到它的众数，众数就是在这个数组中出现次数超过n/2次数的元素，你可以假定这个数组是非空的，并且它一定会有一个满足条件的众数。  
> Credits:  
> Special thanks to @ts for adding this problem and creating all test cases.  
> \#解题思路  
> 要找众数，必然需要两个变量，一个用来保存当前候选的数字，另一个用来保存数字出现的频率，我的做法是使用一个哈希表（Hashtable）用来维护所有的数组以及它们分别出现的频率，然后在这个哈希表中寻找出现频率最大的。  
> 代码如下：

import java.util.Hashtable;
    class Solution {
        public int majorityElement(int[] nums) {
            Hashtable table=new Hashtable(nums.length/2);
            int curr,currmax=0;
            int currcount=0;
            for(int i=0;i<nums.length;i++){
                curr=nums[i];
                if(!table.containsKey(curr)){
                    currcount=1;
                    table.put(nums[i],currcount);
                }else{
                    currcount=(int)table.get(curr);
                    currcount++;
                    table.put(curr,currcount);
                }
                 if(currmax<currcount){
                        currmax=currcount;
                    }
            }
            for(Iterator iterator=table.keySet().iterator();iterator.hasNext();){
                int key=(int)iterator.next();
                int value=(int)table.get(key);
                if(value==currmax){
                    return key;
                }
            }
            return 0;
        }
    }

\#更好的算法  
我及其喜欢这个算法，代码简洁高效，只用了一遍遍历。不过它的核心思想我还没有参透，用这个代码一步步调试过，但是没有时间细细思考为什么这个算法可以得到正确答案，以后有时间了再来挖坟

class Solution {
        public int majorityElement(int[] nums) {
            int count = 0;
            int major = 0;
            for(int val : nums){
                if(count == 0){
                    major = val;
                    count =1;
                    continue;
                }
                if(major == val) {
                    count++;
                }
                else {
                    count--;
                }
            }
            return major;
        }
    }