LeetCode 문제 풀이 day 003 (Jieky)

/*
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
*/
import java.lang.Math;
public class MedianofTwoSortedArrays {
     
	//     ，    
	public double findMedianSortedArrays01(int[] num1,int[] num2){
     
		int n = num1.length;
		int m = num2.length; 
		
		if (n ==0 && m==0){
     
			return -1;
		}
		
		if (n == 0){
     
			if (m%2 == 0){
     
				return (num2[m/2 - 1] + num2[m/2])/2.0;
			}else{
     
				return num2[m/2];
			}
		}
		
		if (m == 0){
     
			if (n%2 == 0){
     
				return (num1[n/2 - 1] + num1[n/2])/2.0;
			}else{
     
				return num2[n/2];
			}
		}
		
		//       
		int[] nums = new int[m + n];
		// i,j   num1、num2     ；count nums     
		int i = 0,j = 0,count = 0;
		while(count < m + n){
     
			// num1       ，   num2    nums
			if (i == n){
     
				while(j < m){
     
					//   count         ，j      
					nums[count++] = num2[j++];
				}
				//          ，    
				break;
			}
			
			//   
			if (j == m){
     
				while(i < n){
     
					nums[count++] = num1[i++];
				}
			}
			
			//           ,i、j         
			if(num1[i] < num2[j]){
     
				nums[count++] = num1[i++];
			}else{
     
				nums[count++] = num2[j++];
			}
		}
		if (count%2 == 0){
     
			return (nums[count/2 - 1] + nums[count/2])/2.0;
		}else{
     
			return nums[count/2];
		}
	}
	
	//                    ，
	//              。
	//              ，     len / 2 + 1  
	public double findMedianSortedArrays02(int[] num1,int[] num2){
     
		int m = num1.length;
		int n = num2.length;
		int len = m + n;
		//         len         ，
		//       ，        ，         
		int left = -1,right = -1;
		// i、j   num1、num2   
		int i = 0, j = 0,count = 0;
		//        ，i、j        
		while(count < len/2 + 1){
     
			left = right;
			//   num1          ，      i。
			//        i,j >= n  num2    。
			if (i < m && (j >= n || num1[i] < num2[j])){
     
				right = num1[i++];
			}else{
     
				right = num2[j++];
			}
			//         
			count++;
		}
		
		if (len % 2 == 0){
     
			return (right + left)/2.0;
		}else{
     
			return right;
		}
	}
	
	//          ？   ？
	//     k       
	public double findMedianSortedArrays03(int[] num1,int[] num2){
     
		// String length   ，int length    
		int n = num1.length;
		int m = num2.length;
		//      ,left、right          
		int left = (n + m + 1) / 2;
		int right = (n + m + 2) / 2; 
		double getKthLeft = getKth(num1,0,n-1,num2,0,m-1,left);
		double getKthRight = getKth(num1,0,n-1,num2,0,m-1,right);
		// n + m     ，left   right  ，          
		return (left + right) / 2.0;
	}
	// start、end、k                    ，
	//       k     
	public double getKth(int[] num1,int start1,int end1,int[] num2,int start2,int end2,int k){
     
		//       ，        (      )，  k=1
		int len1 = end1 - start1 + 1;
		int len2 = end2 - start2 + 1;
		if(len1 > len2){
     
			//       k           ，   num1  
			//            
			return getKth(num2,start2,end2,num1,start1,end1,k);
		}
		
		//         ，      num1，          
		if (len1 == 0){
     
			//              
			return num2[start2 + k - 1];
		}
		
		if(k == 1){
     
			// k=1       
			return Math.min(num1[start1],num2[start2]);
		}
		
		//             ,k/2(    )
		//      ，      ，k             
		int i = start1 + Math.min(len1,k/2) - 1; 
		int j = start2 + Math.min(len2,k/2) - 1; 
		
		//           
		if(num1[i] > num2[j]){
     
			// j  j      
			return getKth(num1,start1,end1,num2,j + 1,end2,k - (j - start2 + 1));
		}else{
     
			// i  i      
			return getKth(num1,i + 1,end1,num2,start2,end2,k - (i - start1 + 1));
		}
	}
	
	public static void main(String[] args){
     
		int[] nums1 = {
     1,2};
		int[] nums2 = {
     3,4};
		
		MedianofTwoSortedArrays instance = new MedianofTwoSortedArrays();
		
		double result = instance.findMedianSortedArrays03(nums1,nums2);
		System.out.println(result);
	}
}