LeetCode之Median of Two Sorted Arrays

桃扇骨 2022-08-05 12:16 197阅读 0赞

题目：There are two sorted arrays A and B 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)).

分析：这题很难，要求时间复杂度为log（m+n）。给出两个已经排好序的数组，要求找出两个数组中的中点元素。想了很久也没有想出怎么做，下面给出了三中解法，第一种是我自己写的，后面两种是我在网上看了，觉得比较好的解法。

代码：

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    //寻找两个已排好序的数组的中点
    class Solution{
    public:
    	int findMedianSortedArrays(int A[], int m, int B[], int n){
    		int total = m + n;
    		int am = 0;
    		int bn = 0;
    		vector<int> arr;
    		for (int i = 0;i<total;i++){
    			if (bn < n && am < m){
    				if (A[am] > B[bn]){
    					arr.push_back(B[bn++]);
    				}else{
    					arr.push_back(A[am++]);
    				}
    			}else if(bn >= n){
    				arr.push_back(A[am++]);
    			}else{
    				arr.push_back(B[bn++]);
    			}
    		}
    		return arr[total/2];
    	}
    	
    	int findMedianSortedArrays2(int A[], int m, int B[], int n){
    		int total = m + n;
    		//判断奇偶，0x1十六进制1
    		if (total & 0x1){ //奇
    			return find_kth(A, m, B, n, total / 2 + 1);
    		}
    		else{ //偶
    			return (find_kth(A, m, B, n, total / 2) + find_kth(A, m, B, n, total / 2 + 1)) / 2.0;
    		}
    	}
    
    	int findMedianSortedArrays3(int A[], int m, int B[], int n){
    		int total = m + n;
    		int* a = new int[total];
    
    		memcpy(a,A,sizeof(int)*m);
    		memcpy(a+m,B,sizeof(int)*n);
    
    		//sort(a,a + total, less<int>());
    		sort(a,a + total);
    		int rtn = a[total>>1]; //除以2，则右移一位
            
    		delete a;
    		return rtn; 
    	}
    private:
    	//递归，求两个数组的中点
    	int find_kth(int A[], int m, int B[], int n, int k) {
    		if (m > n) return find_kth(B, n, A, m, k); //始终认为m<=n（前面数组比后面数组短）,这样便于处理
    		
    		//递归终止条件
    		if (m == 0) return B[k - 1];
    		if (k == 1) return min(A[0], B[0]);
    		
    		//将k划分为两部分
    		int ia = min(k / 2, m);
    		int ib = k - ia;
    		if (A[ia - 1] < B[ib - 1])
    			return find_kth(A + ia, m - ia, B, n, k - ia);
    		else if (A[ia - 1] > B[ib - 1])
    			return find_kth(A, m, B + ib, n - ib, k - ib);
    		else
    			return A[ia - 1];
    	}
    };

都认为第三种解法最好，的确，时间复杂度符合要求。可以说是要背下来的解法，这种解法可以解决求两个已排序数组中第k大的元素。