Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Median of Two Sorted Arrays - LeetCode

 

두 개의 숫자 배열이 주어질 때 전체 숫자의 중간 값을 찾는 문제이다. 이전에 풀었던 문제와 같은 형식의 문제였다. 당시에 풀었던 문제는 클래스를 만드는 문제였고, 이 문제는 중앙 값을 실제로 얻어내는 문제이다. 최종적으로 이번에 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {  
  
        Median med = new Median();  
  
        for(int num: nums1){  
            med.addNum(num);  
        }  
  
        for(int num: nums2){  
            med.addNum(num);  
        }  
  
        return med.calcMedian();  
    }  
  
    private static class Median{  
  
        PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> Integer.compare(b,a));  
        PriorityQueue<Integer> right = new PriorityQueue<>();  
  
        private void addNum(int n){  
            if(left.isEmpty()){  
                left.add(n);  
            }else if(left.peek() > n){  
                left.add(n);  
            }else{  
                right.add(n);  
            }  
  
            while(right.size() > left.size()){  
                left.add(right.poll());  
            }  
  
            while(left.size() > right.size() + 1 ){  
                right.add(left.poll());  
            }  
        }  
  
        private double calcMedian(){  
            if((left.size() + right.size()) % 2 == 1){  
                return left.peek();  
            }else{  
                return (double)(left.peek() + right.peek()) / 2;  
            }  
        }  
    }  
}

 

아래 링크는 예전에 풀어봤던 이와 비슷한 문제와 풀이 내용이다.
https://leetcode.com/problems/find-median-from-data-stream/description/

Find Median from Data Stream - LeetCode

 

당시에 풀었던 내용은 아래와 같다.
https://ygs3004.tistory.com/109

Find Median from Data Stream