Leetcode — 탑 인터뷰 –. 다수 요소

다음과 같이 설명하면 문제가 쉽습니다.

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

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

예 1:

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

예 2:

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

제약사항:

n == 숫자.길이
1 -109 <= 숫자[i] <= 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% 미만.

—

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

다음 포스팅까지! :)

위 내용은 Leetcode — 탑 인터뷰 –. 다수 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!