[LeetCode- Ch.2 정렬 & 검색] 2. K번째 제일 큰 원소 (+ PriorityQueue)

https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/

Kth Largest Element in an Array - LeetCode

 

 

1. 리스트 이용

2. 배열 이용

3. PriorityQueue 이용

 

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
    	List<int[]> list = Arrays.asList(nums);

        Collections.sort(list, Collections.reverseOrder());

        
        return list.get(k-1);
    }
}

-> Int[] -> Integer[] -> list

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
		
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        List<Integer> list = Arrays.asList(arr);
        Collections.sort(list, Collections.reverseOrder());

        
        return list.get(k-1);
    }
}

 

 

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

 

---

배열을 하나씩 넣으면서, 큐의 사이즈가 K번째 값보다 커지면 모두 뺀다 -> 오름차순 정렬

-> pq의 사이즈가 2일 때, 맨 위에 존재하는 요소 -> 2번째 큰 값이 된다. 

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
	    //1
		Queue<Integer> pq = new PriorityQueue<>();
		
		//2
		for(int i: nums) {
			pq.offer(i);
			if(pq.size() >k) {
				pq.poll();
			}
		}
		return pq.peek();
    }
}

 

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int x:nums){
            q.offer(x);
        }
        while(!q.isEmpty()){
            k--;
            if(k==0) return q.poll();
            q.poll();
        }
        return 0;
    }
}