[알고리즘] LeetCode - Majority Element
LeetCode - 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.
입출력 예시
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.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
제약사항
Constraints:
n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1
Solution
[방법1] 정렬후 순차탐색하며 maxCount의 원소 찾기
[방법2] 해쉬맵을 이용하여 각 원소별 횟수 카운팅
[방법3] Boyer-Moore Voting Algorithm (솔루션 참고)
- majority element는 전체 배열의 2/n 개 이상을 차지함.
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
Author And Source
이 문제에 관하여([알고리즘] LeetCode - Majority Element), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jerry92/알고리즘-LeetCode-Majority-Element저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)