leetcode: Median of two sorted Arrays

class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int nums1Length = nums1.length;
		int nums2Length = nums2.length;

		int size = nums1Length + nums2Length;

		int nums1Index = 0;
		int nums2Index = 0;
		int mergedArray[] = new int[size];
		int index = 0;
		while (true) {

			if (nums1Index >= nums1Length && nums2Index >= nums2Length) {
				break;
			} else if (nums1Index >= nums1Length) {
				mergedArray[index++] = nums2[nums2Index++];
			} else if (nums2Index >= nums2Length) {
				mergedArray[index++] = nums1[nums1Index++];
			} else if (nums1[nums1Index] > nums2[nums2Index]) {
				mergedArray[index++] = nums2[nums2Index++];
			} else {
				mergedArray[index++] = nums1[nums1Index++];
			}
		}

		if (size % 2 == 0) {
			return (mergedArray[size / 2] + mergedArray[size / 2 - 1]) / (double) 2;
		}
		return mergedArray[size / 2];
	}
}

N=nums1.length, M=nums2.length라고 두면

위 방법대로 푼다면 시간복잡도는 O(N+M)이 나오고,

mergedArray라는 새 자료구조로 nums1, nums2를 옮겨야 하기 때문에 추가적인 공간 복잡도는 O(N+M)가 된다.

 

 

문제에서는 제시되지 않았으나, nums1, nums2가 정렬되어있다고 치고 이분탐색으로 문제를 푼다면 O(log(N+M)) 풀이도 가능하다.

class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		if (nums2.length < nums1.length) { // 짧은 길이를 nums1로 둔다.
			return findMedianSortedArrays(nums2, nums1);
		}

		int start = 0;
		int end = nums1.length;
		int size = nums1.length + nums2.length;

		while (start < end) {
			int p1 = (start + end) / 2;
			int p2 = (size + 1) / 2 - p1;

			if (p1 == 0 || nums1[p1 - 1] <= nums2[p2]) {
				if (p2 == 0 || nums2[p2 - 1] <= nums1[p1]) {
					break;
				} else {
					start = p1 + 1;
				}
			} else {
				end = p1 - 1;
			}
		}

		int p1 = (start + end) / 2;
		int p2 = (size + 1) / 2 - p1;
		int m = Integer.MIN_VALUE;
		int n = Integer.MAX_VALUE;
		if (size % 2 == 1) {
			return Math.max(p1 - 1 >= 0 ? nums1[p1 - 1] : m, p2 - 1 >= 0 ? nums2[p2 - 1] : m);
		} else {
			return (Math.max(p1 - 1 >= 0 ? nums1[p1 - 1] : m, p2 - 1 >= 0 ? nums2[p2 - 1] : m)
					+ Math.min(p1 < nums1.length ? nums1[p1] : n, p2 < nums2.length ? nums2[p2] : n)) / 2.0;
		}
	}
}

 

 

마지막으로 아래는 O(min(N,M)) 풀이이다. 이 풀이는 이해하기 어렵지만 일단 추가해둔다... 시간날때 읽어봐야지...

leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation

Share my O(log(min(m,n))) solution with explanation - LeetCode Discuss