[LeetCode] 4번: Median of Two Sorted Arrays

문제링크 : https://leetcode.com/problems/median-of-two-sorted-arrays/

 

문제풀이

두 배열을 합쳤을 때 중간 값을 출력하는 문제이다.

홀수 개 일 때는 중간 값 출력, 짝수 개 일 때는 중간 두 값의 평균을 출력한다.

 

문제를 보니 병합정렬이 생각나서 그 방식을 떠올리며 문제를 풀었다.

 

1) nums1과 nums2의 길이를 더한 만큼의 크기로 배열을 생성한다.

 

2) 각 배열의 첫번째 값, nums1[0]과 nums2[0]를 비교한다.

   더 작은 값을 nums 배열에 넣는다.

 

3) 이전 작업에서 nums1[0] 값을 넣었으므로, 다음 값을 비교한다.

   nums1[1]과 nums2[0]을 비교해 더 작은 값을 nums 배열에 넣는다.

 

(이하반복)

 

4) 2~3 작업을 반복하게 되면 nums1 끝까지 비교가 끝나 위와 같은 결과가 나온다.

 

5) 비교를 하지 않은 나머지 값들을 배열에 순서대로 채운다.

 

6) 배열의 중간 값을 반환한다.

 

 

---

 

주어진 두 배열은 이미 정렬된 배열이고,

어차피 중간 인덱스에 해당하는 값 하나 또는 두 개만 구하면 되니까.. 배열을 따로 생성해서 정렬할 필요는 없을 것 같다.

아마 솔루션이 그렇게 풀어져 있는 듯..!. 다음에 풀어봐야지..

 

 

소스코드

https://github.com/jjadekwon/algorithm-java/blob/master/src/leetcode/MedianOfTwoSortedArrays.java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        
        int i, j, k;
        i = j = k = 0;
		int[] nums = new int[length1 + length2];
        while (i < length1 && j < length2) {
        	nums[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        
        if (i == length1) {
        	for (; k < nums.length; k++) {
            	nums[k] = nums2[j++];
            }
        }
        else {
        	for (; k < nums.length; k++) {
            	nums[k] = nums1[i++];
            }
        }
        
        if (nums.length % 2 == 0) return (double)(nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
        else return nums[nums.length / 2];              
    }
}