다음과 같은 설명으로 인해 문제가 발생하기 쉽습니다.

크기 n의 배열 수가 주어지면 다수의 요소를 반환합니다.

주요 요소는 ⌊n / 2⌋회 이상 나타나는 요소입니다. 대부분의 요소가 배열에 항상 존재한다고 가정할 수 있습니다.

예 1:

입력: 숫자 = [3,2,3]
출력: 3

예 2:

입력: 숫자 = [2,2,1,1,1,2,2]
출력: 2

제약조건:

n == 숫자.길이
1 -109

처음에는 지도를 만든 다음 가장 많이 표시되는 지도를 모으는 것에 대해 생각할 것입니다.

가장 많이 나타나는 항목을 정렬하여 얻을 수 있는지 다시 생각해 보세요.

그리고 더 간단한 방법도 있습니다. 설명을 주의 깊게 읽으면 대부분의 요소가 배열의 절반 이상 나타나는 요소라는 것을 이해할 수 있습니다.

이를 염두에 두고 정렬하고 중간 색인을 가져오면 문제가 해결됩니다.

class Solution {
    public int majorityElement(int[] nums) {

        // sort
        Arrays.sort(nums);

        // if by majority element it means that appears more than half of nums size
        // then picking the middle element would be the one that's a majority element
        return nums[nums.length / 2];
    }
}

런타임: 4ms, 다수 요소에 대한 Java 온라인 제출의 54.53%보다 빠릅니다.

메모리 사용량: 53.5MB, 다수 요소에 대한 Java 온라인 제출의 9.23% 미만.

—

그렇습니다! 논의할 다른 사항이 있으면 언제든지 댓글을 남겨주세요. 누락된 부분이 있으면 알려주시면 그에 따라 업데이트할 수 있습니다.

다음 포스팅까지! :)