Description
nums크기 의 배열이 주어지면 다수 요소n 를 반환 합니다 . 과반수 요소는 여러 번 나타나는 요소입니다 . 다수 요소가 항상 배열에 존재한다고 가정합니다.
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
- -2^31 <= nums[i] <= 2^31 - 1
Solution 1. HashTable
public static int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int len = nums.length;
for (int i = 0; i < len; i++) {
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
if(map.get(nums[i]) > len/2) return nums[i];
}
return -1;
}
HashTable을 이용하여 각 숫자별 개수를 카운팅하고 과반이상의 개수가 나온 숫자를 반환합니다.
Solution 2. Sorting(정렬)
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
항상 과반의 수를 포함하기 때문에 정렬 후 중간에 있는 숫자를 반환해줍니다.
Reference
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 133. Clone Graph - 문제풀이 (0) | 2022.02.23 |
---|---|
[LeetCode] 171. Excel Sheet Column Number - 문제풀이 (0) | 2022.02.22 |
[LeetCode] 1288. Remove Covered Intervals - 문제풀이 (0) | 2022.02.20 |
[LeetCode] 402. Remove K Digits - 문제풀이 (0) | 2022.02.18 |
[LeetCode] 39. Combination Sum - 문제풀이 (0) | 2022.02.17 |