leet code (4) - Median of Two Sorted Arrays

알고리즘 풀이 4일차

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

문제설명

두개의 정렬된 배열 nums1 과 nums2 이 주어진다.
두 배열의 중앙값을 구하시오.

중앙값(Median) 이란?
https://ko.wikipedia.org/wiki/중앙값

풀이

중앙값의 개념을 정확히 알지 못하면 헷갈릴 수 있는 문제였다.
두 배열이 이미 정렬된 상태로 주어지기 때문에 머지 소트와 같은 방식으로 배열을 합치고 중앙값을 계산했다.

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] combinedArray = combineArray(nums1, nums2);
            int medianIndex = combinedArray.length / 2;

            if (combinedArray.length % 2 == 0) {
                return (combinedArray[medianIndex - 1] + combinedArray[medianIndex]) / 2.0;
            } else {
                return combinedArray[medianIndex];
            }
        }

        private int[] combineArray(int[] nums1, int[] nums2) {
            int[] combinedArray = new int[nums1.length + nums2.length];

            int nums1Index = 0;
            int nums2Index = 0;
            for (int index = 0; index < combinedArray.length; index++) {
                if (nums1Index == nums1.length) {
                    combinedArray[index] = nums2[nums2Index++];
                } else if (nums2Index == nums2.length) {
                    combinedArray[index] = nums1[nums1Index++];
                } else if (nums1[nums1Index] < nums2[nums2Index]) {
                    combinedArray[index] = nums1[nums1Index++];
                } else {
                    combinedArray[index] = nums2[nums2Index++];
                }
            }
            return combinedArray;
        }
    }

추가

문제 설명을 보면 Follow up 으로 O(log (m+n)) 의 복잡도로 풀라는 이야기가 있다.
위의 방식으로 풀경우 O(m+n) 의 시간이 걸리므로 문제의 의도를 반영한 풀이가 되지못한다.
문제의 의도를 반영한 풀이법은 다음 영상을 참고하면 좋을것같다.
https://www.youtube.com/watch?v=LPFhl65R7ww