Most elements leetcode

Most elements

Method 1 （ Hashtable ）

Use a hash table to store each element and the number of occurrences of the element , When the hash table already has this element , Take the value and add one to the hash table , Finally, you only need to traverse the hash table , Find a key with a value greater than or equal to half the length of the array , Return to .

public static int majorityElement(int[] nums) {
    
        Map<Integer,Integer > map = new HashMap<Integer,Integer >();
        for(int i=0;i<nums.length;i++){
    
            if(!map.containsKey(nums[i])){
    
                map.put(nums[i],1);
            }else{
    
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
    
            if(entry.getValue()>nums.length/2)
                return entry.getKey();
        }
        return 0;
    }

Method 2 （ Sort ）

By sorting the array from small to large , Find the element in the middle of the array , The number of this element must be greater than or equal to half the length of the array .

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

Method 3 （ Moore voting ）

step ：
1、 Maintain a candidate mode candidate And the number of times it appears count. At the beginning candidate It can be any value ,count by 0.
2、 Traversal array nums All elements in , For each element x, In judging x Before , If count The value of is 0, First the x Value assigned to candidate, Subsequent judgment x.
3、 If x And candidate equal , Then the counter count The value of the increase 1; If x And candidate Unequal , Then the counter count The value of is reduced 1.
4、 After traversal ,candidate That is, the mode of the entire array .

public static int majorityElement(int[] nums) {
    
        int count = 0;
        Integer candidate=null;
        for(int num:nums){
    
            if(count==0)
                candidate=num;
            if(num==candidate) count++;
            else   count--;
        }
        return candidate;
    }