Majority Element - 리트코드

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

평가

결과 : 성공
소요시간 : 15분

선형시간 + O(1) 공간복잡도를 낼 수 있는 방법을 생각해봤지만 아이디어를 떠올리지 못했습니다.
풀고 나서도 고민중인데, 공간복잡도를 O(1)로 하는 아이디어를 떠올리지 못하겠습니다.
현재 진행중인 원티드 인턴십에서 답안을 보는걸 권장하지 않아 궁금함을 남긴 채로 넘어가겠습니다 🥲

수도코드

배열 안에 절반 넘게 차지하는 원소를 찾는 문제입니다.
예시로 설명드리면 [1,2,2,1,1,1,1] 배열에서는 7개 중 4개를 차지하고 있는 1을 찾는 문제입니다.

1. 데이터를 정렬합니다.
2. 데이터의 개수가 짝수일 때와 홀수일 때를 분기합니다.
3. 홀수개라면 가운데 위치한 데이터를 포함해야 과반수를 넘길 수 있습니다.
4. 짝수개라면 1번째와 nums.length / 2 + 1 번째 데이터가 같거나,
   혹은 nums.length / 2 와 마지막 데이터가 같아야 과반수를 넘길 수 있습니다.

깔끔한 구조는 아닌데 당장에 생각나는 구조대로 코드를 짜보았습니다.

정답 코드

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        
        // 짝수
        if (nums.length % 2 == 0) {
            int middle1Idx = nums.length / 2;
            int middle2Idx = middle1Idx + 1;
            if (nums[middle1Idx] == nums[nums.length - 1]) {
                return nums[middle1Idx];
            }

            if (nums[middle2Idx] == nums[0]) {
                return nums[0];
            }
        }

        // 홀수
        return nums[nums.length / 2];
    }
}