[LeetCode - Data Structure II] 169. Majority Element

Problem

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

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

Example 2:

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

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

Solution

많이 반복되는 숫자를 찾는 문제이다.

class Solution {
    public int majorityElement(int[] nums) {
        int majorityNum = 0, count = 0;
        for(int num : nums){
            if (count == 0){
                majorityNum = num;
                count++;
            }
            else if (majorityNum == num){
                count++;
            }
            else count--;

        }
        
        return majorityNum;
    }
}

1) majorityNum을 설정해서 초기값을 넣어준다.

2) 초기값이랑 같으면 count++ 다르면 count -- 

3) 결국 많이 반복되는 값이 majorityNum으로 남으면서 답을 도출할 수 있다.

---

다른 사람 풀이)

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

결론

 Arryas.sort를 사용해서 내림차순 정렬을 한 다음 중간값을 찾는 방식으로 코드를 작성했다. 문제를 잘 이해하고 풀이를 작성한 것 같은 느낌을 받아서 앞으로 문제를 풀기 전에 나도 한번 더 생각을 해보는  습관을 가져봐야겠다.

Reference

https://leetcode.com/problems/majority-element