LeetCode之Median of Two Sorted Arrays-蒲公英云

LeetCode之Median of Two Sorted Arrays

桃扇骨 2022-08-05 12:16 291阅读 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];
    }
};