Leetcode 169) Majority Element

24 May 2021 in Algorithms

• Dictionary에 넣으면서 몇번나왔는지 확인. 과반 이상 나왔으면, 바로 리턴해준다.
• 다른 방법에서는 조건인 ‘과반 이상 나온다’를 아주 잘 활용했다.!!

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> m = new HashMap<>();
        if(nums.length==1){
            return nums[0];
        }
        int result=0;
        for(int item : nums){
            if(m.containsKey(item)){
                int val = m.get(item);
                int div = nums.length/2;
                if(val>= div){
                    result=item;
                    break;
                }
                m.put(item, ++val);
            }else{
                m.put(item, 1);
            }
        }
        return result;
    }
}

다른 방법

• 어차피 가장 많은 숫자가 과반 이상 나오니까, 굳이 숫자를 세서 담아 놓지 않고 아래처럼 할 수 있다. 과반이상 나온다는 보장이 없으면 아래처럼 할 수 없다.

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