[LeetCode] Median of Two Sorted Arrays

leetcode.com/problems/median-of-two-sorted-arrays/submissions/

Median of Two Sorted Arrays - LeetCode

2021-01-01

---

import java.util.Arrays;
import java.util.PriorityQueue;
 
public class SolutionMedianOfTwoSortedArrays {
 
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double result = 0;
        int len = nums1.length+nums2.length;
 
        
        int x = 0;
        int y = 0;
        int idx = 0;
        int prev = 0;
        int cur = 0;
        
        while(x < nums1.length || y < nums2.length) { // 71.33%
            if(x < nums1.length && y < nums2.length) {
                if(nums1[x] < nums2[y]) {
                    cur = nums1[x];
                    x++;
                } else {
                    cur = nums2[y];
                    y++;
                }
            } else if(x < nums1.length && y >= nums2.length) {
                cur = nums1[x];
                x++;
            } else if(x >= nums1.length && y < nums2.length) {
                cur = nums2[y];
                y++;
            }
            if(idx == len/2) break;
            idx++;
            prev = cur;
        }
        
        if(len % 2 == 0) result = (prev+cur) / 2.0;
        else result = cur;
        
       
// (2) using array         
        int merge[] = new int[len];
        while(x < nums1.length || y < nums2.length) { // 57.55%
            if(x < nums1.length && y < nums2.length) {
                if(nums1[x] < nums2[y]) {
                    merge[idx] = nums1[x];
                    x++;
                } else {
                    merge[idx] = nums2[y];
                    y++;
                }
            } else if(x < nums1.length && y >= nums2.length) {
                merge[idx] = nums1[x];
                x++;
            } else if(x >= nums1.length && y < nums2.length) {
                merge[idx] = nums2[y];
                y++;
            }
            if(idx == len/2) break;
            idx++;
        }
        if(len % 2 == 0) {
            result = (merge[len/2] + merge[len/2-1]) / 2.0;
        } else result = merge[len/2];
 
//    (3) using priorityqueue
        
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for(int i = 0; i < nums1.length; i++) q.add(nums1[i]);
        for(int i = 0; i < nums2.length; i++) q.add(nums2[i]);
        
        for(int i = 0; i < len; i++) {
            merge[i] = q.poll();
        }
        
        if(len % 2 == 0) {
            result = (merge[len/2] + merge[len/2-1]) / 2.0;
        } else result = merge[len/2];
        
        
        return result;
    }
    
    public static void main(String[] args) {
        int n[] = {1,2};
        int n2[] = {3,4};
    
        System.out.println(findMedianSortedArrays(n, n2));
    }
}
 

#문제풀이

(3) 맨 처음에는 priorityqueue로 풀었다. 단순하게 priorityqueue에 두 개의 배열 값을 넣었고, 알맞는 중간값을 출력했다. 간단하고 편한 방법이긴 하지만 시간이 너무 오래걸렸다.

 

(2) 두 번째로는 새로운 merge 배열을 만들어서 두 개의 배열을 하나로 합쳤다.  두 개의 배열을 탐색하면서 새로운 배열을 만드는 로직으로 짰다. 각각의 배열을 위한 인덱스 변수 x, y 를 선언하고, x,y 인덱스 값에 따라 조건을 주어서 순서에 맞게 merge array를 만들었다. 

 

(1) 그런데 메모리 사용률이 좀 높아서 배열을 빼고 단순히 변수로 계산을 했다. cur와 prev 변수를 만들어서, cur는 현재 index에 해당하는 값, prev는 그 전 값을 저장했다. prev를 사용하는 이유는 두 배열의 길이의 합이 짝수인 경우 (cur + prev) / 2.0으로 계산해야 되기 때문이다. 

 

+) 마지막 방법으로 하면 다음과 같은 결과를 얻을 수 있다.

Runtime: 2 ms, faster than 99.71% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 71.33% of Java online submissions for Median of Two Sorted Arrays.