How to get O(log(m+n)) complexity? I only solved it in O(m+n)


  • 0
    H

    My naive solution is just merge two array and find the median. Obvious we can do better. But I just have no idea about it.


  • 1
    S

    Here is 1337's post about this problem.


  • -6
    F
    This post is deleted!

  • 1
    Z

    Below is my O(log(n+m))algorithm.The main idea is using binary search to find the key number's position.

    class Solution {
    public:
    	double findMedian(int A[], int m) {
    		if(m%2==1) return A[m/2];
    		return (A[m/2-1] + A[m/2]) / 2.0;
    	}
    	bool findMedianOdd(int A[], int m, int B[], int n, double &res) {
    		int left = -1, right = m, half = (n + m) / 2;
    		while(true) {
    			int mid = (left + right) / 2;
    			if(mid > half) {
    				right = mid; continue;
    			}
    			int num = half - mid;
    			if(num > n) {
    				left = mid; continue;
    			}
    			if((num<=0 || B[num-1]<=A[mid]) && (num>=n || B[num]>=A[mid])) {
    				res = A[mid];
    				return true;
    			}
    			if(num<=0 || B[num-1]<=A[mid]) {
    				right = mid;
    			} else {
    				left = mid;
    			}
    			if(left+1 >= right) break;
    		}
    		return false;
    	}
    	bool findMedianEven(int A[], int m, int B[], int n, double &res) {
    		int left = -1, right = m, half = (n + m) / 2;
    		while(true) {
    			int mid = (left + right) / 2;
    			if(mid > half) {
    				right = mid; continue;
    			}
    			int num = half - mid;
    			if(num > n) {
    				left = mid; continue;
    			}
    			if((num<=0 || B[num-1]<=A[mid]) && (num>=n || B[num]>=A[mid])) {
    				int tmp;
    				if(num<=0) tmp = A[mid-1];
    				else if(mid==0) tmp = B[num-1];
    				else tmp = max(A[mid-1], B[num-1]);
    				res = (tmp + A[mid]) / 2.0;
    				return true;
    			}
    			if(num<=0 || B[num-1]<=A[mid]) {
    				right = mid;
    			} else {
    				left = mid;
    			}
    			if(left+1 >= right) break;
    		}
    		return false;
    	}
    	double findMedianSortedArrays(int A[], int m, int B[], int n) {
    		if(m==0) return findMedian(B, n);
    		if(n==0) return findMedian(A, m);
    		double res;
    		if((m+n) % 2 == 1) { //sample A={1, 3}, B = {2, 4, 5}, so use binary search to find 4
    			if(findMedianOdd(A, m, B, n, res)) return res;
    			findMedianOdd(B, n, A, m, res); return res;
    		} else { ////sample A={1, 3}, B = {2, 4}, so use binary search to find 3
    			if(findMedianEven(A, m, B, n, res)) return res;
    			findMedianEven(B, n, A, m, res); return res;
    		}
    		return -9999999.90;
    	}
    }ttt;
    

  • 1
    C

    Here is my Solution based on finding the kth element in two sorted arrays. Get rid of at least (m+n)/4 elements each time by using a binary search. T(m+n) <= T(3/4*(m+n)) + O(lg(m+n)), so the time complexity is O(lg(m+n)).

    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            if ((m+n) % 2 == 1)
                return findkthElement(A, m, B, n, (m+n)/2+1);
            else
                return (findkthElement(A, m, B, n, (m+n)/2) + findkthElement(A, m, B, n, (m+n)/2+1))/2.0;
        }
        
        int findkthElement(int A[], int m, int B[], int n, int k) {
            if (m == 0) return B[k-1];
            if (n == 0) return A[k-1];
            if (k == 1) return min(A[0], B[0]);
            if (m < n) return findkthElement(B, n, A, m, k);
            int i = m/2;
            int low = 0, high = n-1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (B[mid] <= A[i]) low = mid + 1; else high = mid - 1;
            }
            int j = high; //B[j] is the maximum number which <= A[i]
            if (i+j+2 == k) //i+j+2 is the rank of A[i]
                return A[i];
            else if (i+j+2 < k)
                return findkthElement(A+i+1, m-i-1, B+j+1, n-j-1, k-i-j-2);
            else
                return findkthElement(A, i, B, j+1, k);
        }
    };

  • -2
    S

    I use the select sort method to solve this problem, two 'pointer' to record the current position of two arrays, each time put a smaller one into merged array. Here is my Java code.

    public double findMedianSortedArrays(int A[], int B[]) {
    	int m = A.length;
    	int n = B.length;
    	int[] merge = new int[m+n];
    	int currentA = 0, currentB = 0;
    	for(int i = 0; i < m+n; i++){
    		if(currentA < m && currentB <n){
    			if(A[currentA] < B[currentB]){
    				merge[i] = A[currentA];
    				currentA++;
    			}else if(A[currentA] > B[currentB]){
    				merge[i] = B[currentB];
    				currentB++;
    			}else{
    				merge[i] = A[currentA];
    				merge[i+1] = A[currentA];
    				currentA++;
    				currentB++;
    				i++;
    			}
    		}else if(currentA == m){
    			merge[i] = B[currentB];
    			currentB++;
    		}else if(currentB == n){
    			merge[i] = A[currentA];
    			currentA++;
    		}
    	}
    	if((m + n) % 2 == 0){
    		return ((double)merge[(m+n)/2] + (double)merge[(m+n)/2-1])/2;
    	}else{
    		return merge[(m+n)/2];
    	}
    }

  • 0
    L

    Unfortunately, your algorithm is O(log(m+n)*log(m+n)), not O(log(m+n)). T(m+n) <= T(3/4*(m+n)) + O(lg(m+n)) is not acceptable, you should optimize it into T(m+n) <= T(3/4*(m+n)) + O(1) and then the final complexity will be O(log(m+n)).


  • 0
    C

    You are right. Thanks a lot for pointing out my careless mistake.


  • 8
    W

    You can reuse the algorithm which solves Find the k-th Smallest Element in the Union of Two Sorted Arrays.

    My implementation below used binary search to maintain the invariant (i + j = k – 1), so the complexity is O(log k) = O(log((m+n)/2)) = O(log(m+n))

    class Solution {
    public:
        int findKth(int A[], int m, int B[], int n, int k) {
            int l = k - 1 - min(k - 1, n), r = min(k, m);
            while (l <= r) {
                int i = l + ((r - l) >> 1);
                int j = k - 1 - i;
                if (i >= 0 && i < m && (j >= n || A[i] <= B[j]) && (j == 0 || B[j-1] <= A[i]))
                    return A[i];
                else if (j >= 0 && j < n && (i >= m || B[j] <= A[i]) && (i == 0 || A[i-1] <= B[j]))
                    return B[j];
                if (j >= n || A[i] < B[j]) l = i + 1;
                else r = i - 1;
            }
        }
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            if ((m + n) & 1) return findKth(A, m, B, n, ((m + n) >> 1) + 1);
            else return (findKth(A, m, B, n, (m + n) >> 1) + findKth(A, m, B, n, ((m + n) >> 1) + 1)) * 0.5;
        }
    };
    

  • 0
    B

    Sounds great! But I solve this problem in O(m+n) and accepted


  • 0
    N

    Could you explain the definition of l and r here? I am confused with it.


  • 0
    W

    l and r are the boundries of i, i is the index of A's element that satisfied the invariant (i + j = k – 1).


  • 0
    X
    This post is deleted!

Log in to reply
 

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