[LeetCode] 169. Majority Element

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

Majority Element - LeetCode

문제 유형 : 배열

문제 난이도 : Easy

 

문제

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.

 

n의 크기를 가진 배열 nums가 있습니다. 가장 많은 요소를 반환하시오. 가장 많은 요소는 n/2개 이상 차지합니다.

 

풀이

1. 만약 정렬되어 있는 배열이라면, n/2개 이상인 요소의 값은 무조건 배열의 중앙에 하나 위치하게 되어있다. 정렬하고, 가운데를 반환하면 된다.

 

2. 0인덱스부터 순회를 시작한다. 기준을 현재 숫자로 두고, 현재 숫자가 이전과 같으면, 그 숫자에 대해서 1점을 누적시키고, 아니라면 1점을 뺀다.

점수가 0이되면 현재 숫자로 기준을 바꾼다. 순회를 다 돌면 절반 이상을 채운 숫자가 기준인 채로 반환될 것 이다.

 

코드(C++)

1. 정렬을 이용한 풀이

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

2. 포인트를 이용한 풀이

class Solution {
public:
    int majorityElement(vector<int>& arr) {
        int ele=arr[0];
        int count=0;
        for(int i=0;i<arr.size();i++){
            if(count==0)ele=arr[i];
            count+=(ele==arr[i])?1:-1;
        }
        return ele;
    }
};