[LeetCode] Majority Element

오늘의 문제. 

leetcode.com/problems/majority-element/

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 이상 나타나는 요소이다. 
배열에서 항상 존재한다고 가정할 수 있다.

Constraints:
1. n == nums.length
2. 1<= n <= 5*10^4
3. -2^31 <= nums[i] <= 2^31-1

Follow-up: Could you solve the problem in linear time and in O(1) space? 

해시맵으로 풀까.. 하다가 해시맵 안 쓰고 풀어보기로 했다. 해시맵 써서도 풀어보면 좋을 거 같음. 요새 해시맵에 갇혔다. 이전에 알게 된 Arrays.sort()함수를 써서 정렬해주고서 풀었다. 모범답안을 보니까 엄청 깔끔하던데... 

import java.util.Arrays;

public class cote0319_169_MajorityElement {
    public int majorityElement(int[] nums) {
        /*
            ~ 의식의 흐름 ~
            nums배열의 숫자들 중 nums.length / 2 보다 많이 포함된 숫자가 있으면 그걸 리턴하면 됨
            일단 포문을 돌아서 해시맵에 저장을 해볼까 아님 해시맵 안쓰고서 풀어볼까
        */

        //일단 정렬 시켜준다
        Arrays.sort(nums);

        //배열이 1개짜리면 바로 리턴
        if(nums.length < 2){
            return nums[0];
        }

        //각 요소가 몇개까지 반복되나 카운트
        int count=0;
        for(int i=0; i<nums.length-1; i++){
            if(nums[i]==nums[i+1]){
                count++;
            }
            if(count>nums.length/2){
                return nums[i];
            }
        }
        //사실 여기서 리턴되면 마조리티 엘리먼트가 없는 것임
        return -1;
    }
}

 

Discussion 모범답안, 좀 이해하기 어렵다. 

class Solution {
    public int majorityElement(int[] nums) {
        int maj = nums[0];
      	//첫번째 숫자를 별도 변수에 지정한다
        
        int count = 1;
        //어쨌든 한개는 있을테니까 count는 1
        
        for(int i=1; i<nums.length; ++i) { //0번째는 지정해줬으니 1번째부터 비교 시작
            if(maj==nums[i]) count++; //지정된 maj와 다음 숫자가 같으면 카운트를 플러스
            else if(count>0) --count; //같지 않고 카운트가 0보다 크면 카운트를 마이너스.
            //근데 여기서 왜 --count를 했는지 모르겠다. 리트코드에서 돌려보니 count--; 해도 똑같이 억셉된다.
            else { maj = nums[i]; count=1; }
        }
        count=0;
        
        for(int n : nums) if(n==maj) count++; 
        if(2*count>nums.length) return maj;
        
        return -1;
    }
}

 

그리고 보고서 헐 했던 답안. 아 진짜 이러면 되겠구나... 어차피 sort해주면 같은애들끼리 다 모여서 majority element가 절반이상일 테니까 무조건 절반값을 리턴해주면 된다.

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