본문 바로가기

LeetCode/Heap

 (7)
[Medium] 378. Kth Smallest Element in a Sorted Matrix (아마존) #문제 설명 378번 문제는 정수 k와 n x n 정사각형 matrix가 주어지고, matrix의 각 칸에는 정수들이 담겨있다. 이 문제에서는 matrix안에서 정수 k번째로 작은 정수들을 전부 return해주면 된다. 예를 들어 [[1,5,9], [10,11,13] , [12,13,15]] 라는 2d 매트릭스가 주어지고 정수 k = 4가 주어지면, matrix안의 4번째로 작은 10을 return해주면 된다. #문제 풀이 class Solution { public int kthSmallest(int[][] matrix, int k) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for(int i = 0; i < matr..
[Medium] 703. Kth Largest Element in a Stream (아마존 코딩 테스트 기출 문제) #문제 설명 Leetcode 703번문제는 int k 와 정수 array가 주어진다. 또한 이 array는 stream이기때문에 계속 정수들을 array에 추가 시킨다. 이 문제에서는 주어진 array에 여러개의 정수를 add하고, add가 끝난뒤 array에서 k번째로 큰 정수값을 반환시켜주면된다. #문제 풀이 class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { minHeap = new PriorityQueue(); this.k = k; for(int i = 0; i < nums.length;i++){ minHeap.add(nums[i]); if(minHeap.size(..
[Hard] 295. Find Median from Data Stream (Microsoft 기출 문제) #문제 설명 #문제 풀이 class MedianFinder { PriorityQueue minHeap = new PriorityQueue(); PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); public MedianFinder() { } public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll()); } public double findMedian() { if (maxHeap.size() > minHeap.size()) retu..
[Medium] 451. Sort Characters By Frequency #문제 설명 #문제 풀이 HashMap + Heap class Solution { public String frequencySort(String s) { Map map = new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } PriorityQueue pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a)); for (char c : map.keySet()) { pq.offer(c); } StringBuilder sb = new StringBuilder(); while (!pq.isEmpty()) { char c = pq.poll(); for (int i ..
[Medium] 1046. Last Stone Weight (구글 코딩 테스트 기출문제) #문제 설명 #문제 풀이 class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); int sum = 0; for(int i = 0; i 1){ int num1 = 0; int num2 = 0; if(maxHeap.size() >= 2){ num1 = maxHeap.poll(); num2 = maxHeap.poll(); } m..
[Medium] 347. Top K Frequent Elements (애플/MS/메타/아마존) #문제 설명 Leetcode 347번 문제는 array와 정수 k가 주어진다. 배열에서 가장 빈도가 높은 k개의 요소를 return하면된다. 예를 들어 [1,1,1,2,2,3]이 라는 배열에 k=2가 주어지면 1 (빈도 3번) 과 2 (빈도 2번)을 반환해주면 된다. 만약 k=3이라면 1,2,3 모두 반환 해주면 된다 #문제 풀이 class Solution { public int[] topKFrequent(int[] nums, int k) { // O(1) time if (k == nums.length) { return nums; } // 1. build hash map : character and how often it appears // O(N) time Map count = new HashMap()..
[Medium] Kth Largest Element in an Array (아마존/구글) #문제 설명 Leetcode 215번 문제는 정수로 채워진 배열 nums와 정수 k가 주어진다. 주어진 배열안에서 k번째로 큰 정수를 return하면 된다. 위에 예시를 보면 [3,2,1,5,6,4] 의 배열과 k=2가 주어진다 이경우 에는 배열에서 2번째로 큰 숫자를 return하면 되기에 5를 return해야한다. #문제 풀이 Min-heap 풀이: class Solution { public int findKthLargest(int[] nums, int k) { //min-heap PriorityQueue minHeap = new PriorityQueue(); for(int i = 0; i < k;i++){ minHeap.add(nums[i]); } for(int i = k; i < nums.leng..

티스토리툴바