크기가 n 인 배열 nums가 주어지면 과반수의 element를 반환합니다.
과반수의 element ⌊n / 2⌋ 번 이상 나타나는 요소입니다.
과반수의 element 항상 배열에 존재한다고 가정 할 수 있습니다.
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
sudo code
element.count > [n/2]인거 구하기
element.count부터 구해야겠다
-> testcase [3,2,3] -> [3,2],[2,1] & [2,2,1,1,1,2,2] -> [2,4],[1,3] -> map... hashmap
저번에 했던 getOrDefault로 key값에 더하는 식으로 정렬하고
거기서 가장 큰 value를 뽑아서 key를 리턴하는 식으로 가봅시다
1차시도 (Collections.max써가지고 getKey하면 구해진다는데 아닌가?)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums){
map.put(n,map.getOrDefault(i,0) + 1);//storing num and its freq
}
return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}2차시도 (??? MaxValue랑 비교해서 그 maxValue의 Key를 가져오라고 명시적으로 해둔거같은데?)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
int result = 0;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums)
{
map.put(n,map.getOrDefault(i,0) + 1);//storing num and its freq
}
// 정렬 (3,2) (2,1) -> 여기서 value가 가장 높은거 고르면 return or n>2이면 리턴
int maxValueInMap=(Collections.max(map.values()));
for (Map.Entry<Integer, Integer> entry : map.entrySet())
{
if (entry.getValue()==maxValueInMap)
{
result = entry.getKey();
return entry.getKey();
}
}
return result;
}
}3차시도 (map 넣을때 변수를 잘못 설정하였다 ㅠㅠ크기가 n 인 배열 nums가 주어지면 과반수의 element를 반환합니다.
과반수의 element ⌊n / 2⌋ 번 이상 나타나는 요소입니다.
과반수의 element 항상 배열에 존재한다고 가정 할 수 있습니다.
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
sudo code
element.count > [n/2]인거 구하기
element.count부터 구해야겠다
-> testcase [3,2,3] -> [3,2],[2,1] & [2,2,1,1,1,2,2] -> [2,4],[1,3] -> map... hashmap
저번에 했던 getOrDefault로 key값에 더하는 식으로 정렬하고
거기서 가장 큰 value를 뽑아서 key를 리턴하는 식으로 가봅시다
1차시도 (Collections.max써가지고 getKey하면 구해진다는데 아닌가?)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums){
map.put(n,map.getOrDefault(i,0) + 1);//storing num and its freq
}
return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
2차시도 (??? MaxValue랑 비교해서 그 maxValue의 Key를 가져오라고 명시적으로 해둔거같은데?)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
int result = 0;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums)
{
map.put(n,map.getOrDefault(i,0) + 1);//storing num and its freq
}
// 정렬 (3,2) (2,1) -> 여기서 value가 가장 높은거 고르면 return or n>2이면 리턴
int maxValueInMap=(Collections.max(map.values()));
for (Map.Entry<Integer, Integer> entry : map.entrySet())
{
if (entry.getValue()==maxValueInMap)
{
result = entry.getKey();
return entry.getKey();
}
}
return result;
}
}
3차시도 (map 넣을때 변수를 잘못 설정하였다 ㅠㅠ)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
int result = 0;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums)
{
map.put(i,map.getOrDefault(i,0) + 1);//storing num and its freq
}
// 정렬 (3,2) (2,1) -> 여기서 value가 가장 높은거 고르면 return or n>2이면 리턴
int maxValueInMap=(Collections.max(map.values()));
for (Map.Entry<Integer, Integer> entry : map.entrySet())
{
if (entry.getValue()==maxValueInMap)
{
result = entry.getKey();
return entry.getKey();
}
}
return result;
}
}
Runtime: 18 ms, faster than 8.97% of Java online submissions for Majority Element.
Memory Usage: 54.2 MB, less than 8.44% of Java online submissions for Majority Element.4차시도 (아까 쓴 함수를 쓰니 시간 및 공간 복잡도가 많이 올려갔다)
class Solution {
public int majorityElement(int[] nums) {
// nums의 길이 & 구하는 값의 count가 n/2 이상
int n = nums.length;
int result = 0;
//제약조건 1<n<50000 & nums[i]-> int 범위-> int 범위
// testcase Ex1 [3,2],[2,1] Ex2 [2,4], [1,3] -> Map
// 저번 hashMap활용해보자
Map<Integer,Integer> map = new HashMap();
for(int i : nums)
{
map.put(i,map.getOrDefault(i,0) + 1);//storing num and its freq
}
// 정렬 (3,2) (2,1) -> 여기서 value가 가장 높은거 고르면 return or n>2이면 리턴
return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
Runtime: 9 ms, faster than 35.09% of Java online submissions for Majority Element.
Memory Usage: 44.6 MB, less than 25.66% of Java online submissions for Majority Element.
'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode] Convert Binary Number in a Linked List to Integer (0) | 2021.04.03 |
|---|---|
| [LeetCode] - Merge Two Sorted Lists (0) | 2021.03.26 |
| HashMap Sorting in java (0) | 2021.03.18 |
| [LeetCode] Lemonade Change (1) | 2021.03.17 |
| [LeetCode] Two Sum (0) | 2021.03.16 |