[LeetCode/Easy] 169. Majority Element

1. Input

1) int[] nums

 

2. Output

1) nums의 요소 중 그 개수가 nums의 길이의 절반보다 더 많은 요소를 반환

 

3. Constraint

1) n == nums.length

2) 1 <= n <= 5 * 10^4

3) -10^9 <= nums[i] <= 10^9

 

4. Example

Input: nums = [2,2,1,1,1,2,2] -> Output: 2

Input: nums = [3,2,3] -> Output: 3

 

5. Code

1) 첫 코드(2023/05/13)

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i : nums)
            map.put(i, map.getOrDefault(i,0)+1);
        Iterator it = map.entrySet().iterator();
        int ans = 0;
        while(it.hasNext()){
            Map.Entry e = (Map.Entry)it.next();
            if((int)e.getValue()>nums.length/2){
                ans = (int)e.getKey();
                break;
            }
        }
        return ans;
    }
}

2) O(1)으로 못 풀어서 찾아 본 다른 사람의 코드(2023/05/13)

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