(leetcode) 4.Median of Two Sorted Arrays

문제.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted      arrays.

The overall run time complexity should be O(log (m+n)).

 

정렬된 int 배열 nums1, nums2 가 주어질 때 이 배열들을 합친 정렬된 배열의 중앙 값을 구하는 문제

시간 복잡도는 O(log)를 요구한다.

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

 

풀이.

 

Constraints를 봤을 때 둘 다 빈배열 일 수는 없으므로(1 <= m + n <= 2000) 0을 나눌때 발생하는 예외는 배제.

검색에 대한 문제, 시간 복잡도로 봤을 때 이진 검색을 통해서 해결 할 수있다.

 

짝수 배열

1

2

3

4

홀수 배열

1

2

3

 

중앙 값을 구하는 문제이므로 짝 수 배열은 두 개의 합을 나눈 값, 홀수 배열은 중앙 값을 찾으면 되는 문제 

class Solution {
    public double findMedianSortedArrays(int[] num1, int[] num2) {
    
        
        double result = 0;
				
		int[] mergeArray = new int[num1.length+num2.length];
		
        //int 배열을 인자로 받기 때문에 arraycopy를 이용해서 합쳐준다
		System.arraycopy(num1, 0, mergeArray, 0, num1.length);
		System.arraycopy(num2, 0, mergeArray,num1.length, num2.length);
        //정렬
		Arrays.sort(mergeArray);
        
		if(mergeArray.length%2==0) {
			result = mergeArray[mergeArray.length/2-1]+mergeArray[mergeArray.length/2];
			result = result/2;
		}else {
			result = mergeArray[mergeArray.length/2];
		}
        
        return result;
    }
}