JAVA----------------------Easy Version To Understand!!


  • 19
    H
    public static int findKthSmallest(int[] a, int m, int begin1, int[] b, int n, int begin2, int k) {
    
    	if (m > n)
    		return findKthSmallest(b, n, begin2, a, m, begin1, k);
    	if (m == 0)
    		return b[begin2 + k - 1];
    	if (k == 1)
    		return Integer.min(a[begin1], b[begin2]);
    	int partA = Integer.min(k / 2, m), partB = k - partA;
    	if (a[begin1 + partA - 1] == b[begin2 + partB - 1])
    		return a[begin1 + partA - 1];
    	else if (a[begin1 + partA - 1] > b[begin2 + partB - 1])
    		return findKthSmallest(a, m, begin1, b, n - partB, begin2 + partB, k - partB);
    	else
    		return findKthSmallest(a, m - partA, begin1 + partA, b, n, begin2, k - partA);
    
    }
    
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    	int len1 = nums1.length, len2 = nums2.length, sumLen = len1 + len2;
    	if (sumLen % 2 != 0) {
    
    		return findKthSmallest(nums1, len1, 0, nums2, len2, 0, sumLen / 2 + 1);
    	} else {
    		return (findKthSmallest(nums1, len1, 0, nums2, len2, 0, sumLen / 2)
    				+ findKthSmallest(nums1, len1, 0, nums2, len2, 0, sumLen / 2 + 1)) / 2.0;
    	}
    
    }

  • 0
    H

    good answer!well done!


  • 0
    L

    I think the recursive calling still can be optimized. The array length of smaller value can be reduced from m to partA, and the array length of bigger value can be from n to partB. But here you still keep the array size.


  • 0
    X

    your algorithm is excellent!


  • 0
    Q

    Great solution!
    @LionelWang agreed, can be optimized like this

        	else if (a[begin1 + partA - 1] > b[begin2 + partB - 1])
        		return findKthSmallest(a, partA, begin1, b, n - partB, begin2 + partB, k - partB);
        	else
        		return findKthSmallest(a, m - partA, begin1 + partA, b, partB, begin2, k - partA);
    

  • 0
    G

    I want to know why java program doesn't have a {public static void main()}
    ----from a newer


  • 0
    K
    public class Solution {
        public static int[] sort(int[] ori) {
    		for (int i = 0; i < ori.length; i++) {
    			for (int j = i; j < ori.length; j++) {
    				if (ori[i] > ori[j]) {
    					int temp = ori[i];
    					ori[i] = ori[j];
    					ori[j] = temp;
    				}
    			}
    		}
    		return ori;
    	}
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
    		int len2 = nums2.length;
    		int sumLen = len1 + len2;
    		int[] sumArray = new int[sumLen];
    		for (int i = 0; i < len1; i++) {
    			sumArray[i] = nums1[i];
    		}
    		for (int j = 0; j < len2; j++) {
    			sumArray[j + len1] = nums2[j];
    		}
    		for (int i = 0; i < sumArray.length; i++) {
    			System.out.print(sumArray[i]);
    		}
    		int[] sortedArray = sort(sumArray);
    		if (sumLen%2==0) {
    			return (sortedArray[(sumLen/2)-1]+sortedArray[(sumLen/2)])/2.0;
    		}
    		else{
    			return sortedArray[(sumLen/2)];
    		}
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.