참고
문제해설
NOTE
•
입력 값 ⇒ 정수배열과 정수 k
•
출력 값 ⇒ 배열에서 k번째로 큰 요소를 반환한다.
•
정렬을 사용하지 않고 해결해야 한다!
문제 로직고민
NOTE
1.
가장 무식한 방법이지만 배열 크기 n을 k만큼 탐색하면 가능하다.
•
시간복잡도가 n^2이지만 가장 단순한 해결방법이다.
•
하지만 배열의 최대길이가 10만이고, k역시 근접할 수 있으므로 불가능한 방법이다.
2.
Tree를 이용한 방식
•
MaxHeap구조를 만들어서 최대값을 k번 뽑아냈을때의 결과를 반환하면된다.
•
Heap구조를 만드는 시간복잡도는 N이며, 최대값을 뽑는 과정은 log N이다.
•
최종적으로 N의 시간이 걸리므로 1번보다 더 효율적이다.
작성코드
NOTE
class Solution {
public int findKthLargest(int[] nums, int k) {
MaxHeap heap = new MaxHeap(nums, nums.length);
int result =0;
for(int i=0; i<k; i++){
result = heap.pop();
}
return result;
}
}
class MaxHeap{
int[] array;
int n;
MaxHeap(int[] arr, int size){
array = arr;
n = size;
heapify();
}
public void heapify(){
for(int i=(n-2)/2; i >=0; i--){
bubbleDown(i);
}
}
public int pop(){
int result = array[0];
swap(0, n-1);
n--;
bubbleDown(0);
return result;
}
private void bubbleDown(int i){
int left = i*2 + 1;
int right = i*2 + 2;
int root = i;
if(left < n && array[root] < array[left]) root = left;
if(right < n && array[root] < array[right]) root = right;
if(root != i){
swap(root, i);
bubbleDown(root);
}
}
private void swap(int a, int b){
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
Java
복사
Heap구현을 최근에 연습해서 금방해결함
정답코드
NOTE
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums) {
if(minHeap.size() < k) {
minHeap.offer(num);
}
else if (num > minHeap.peek()){
minHeap.poll();
minHeap.offer(num);
}
}
return minHeap.peek();
}
}
Java
복사
메모리를 적게 사용하는 코드
•
상위 코드들이 대부분 정렬 혹은 우선순위 큐를 그대로 사용한거라 크게 참고할게 없었다.