공부 기록

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

최소 거리를 구하는 방법보다는 최소 거리를 찍어놓고 그 거리가 가능한지 여부를 확인한다.

풀이 로직은 아래와 같다.

1. 이분탐색으로 가능한 거리 mid를 찍는다.

2. 없앨 돌의 수(remove)를 계산한다 - 돌 사이의 거리가 mid보다 짧으면 없애서 돌 사이의 거리를 늘린다.

3. 없앨 돌의 수가 n보다 큰 경우 돌 사이가 더 가깝다는 의미이므로 왼쪽탐색, n보다 작거나 같은 경우는 오른쪽을 탐색하면서 업데이트

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int distance, int[] rocks, int n) {
		List<Integer> rock = Arrays.stream(rocks).boxed().collect(Collectors.toList());
		rock.add(0);
		rock.add(distance);
		Collections.sort(rock);

		int right = distance;
		int left = 0;
		int mid = 0;
		int answer = 0;

		while (left <= right) {
			mid = (right + left) / 2;
			int remove = 0;

			int i = 0;
			int j = 1;
			while (i < rock.size() && j < rock.size()) {
				if (rock.get(j) - rock.get(i) < mid) {
					remove++;
					j++;
				} else {
					i = j;
					j++;
				}
				if (remove > n) {
					break;
				}
			}

			if (remove <= n) {
				left = mid + 1;
				answer = Math.max(answer, mid);
			} else {
				right = mid - 1;
			}

		}

		return answer;
	}
}