leetcode_median_of_two_sorted_arrays

发表于

难度：Hard

题目要求时间复杂度O(log(m+n))。考虑用二分查找，因为是两个数组，可以分别比较k/2的元素，则较小元素及其之前的元素是k/2小的元素之内的。递归调用时，要注意将index+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size()+nums2.size();
        if(len % 2 == 0)
            return (find_k_th_element(nums1,0,nums2,0,len/2)+find_k_th_element(nums1,0,nums2,0,len/2+1))*0.5;
        else
            return find_k_th_element(nums1,0,nums2,0,len/2+1);
    }
    int find_k_th_element(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)
    {
        int m = nums1.size();
        int n = nums2.size();
        if(i >= m)
            return nums2[j+k-1];
        if(j >= n)
            return nums1[i+k-1];
        if(k == 1)
            return min(nums1[i],nums2[j]);
        int ii = min(i+k/2-1,m-1);
        int jj = min(j+k/2-1,n-1);
        if(nums1[ii] < nums2[jj])
        {
            cout<<k-(ii-i+1)<<endl;
            return find_k_th_element(nums1, ii+1, nums2, j, k-(ii-i+1));
        }
        else
        {
            cout<<k-(jj-j+1)<<endl;
            return find_k_th_element(nums1, i, nums2, jj+1, k-(jj-j+1));
        }
    }
};

解题思路：考虑两种情况。

[1 2 3 4]    [5 6 7]    先比较三次，找出三个最小的，则第四个即为解 -> 4

[1 2 3 4] [5 6 7 8]    先比较三次，找出三个最小的，则第四、五个即为解-> (4+5)/2

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size_1 = nums1.size();
        int size_2 = nums2.size();
        int step = (size_1 + size_2) / 2;
        int  calculate_times = ((size_1 + size_2) % 2 == 0) ? 2:1;
        int index_1 = 0;
        int index_2 = 0;
        if(calculate_times == 2) step--;
        while(step--)
        {
            if(index_1 != size_1 && index_2 != size_2)
            {
                if(nums1[index_1] < nums2[index_2])
                {
                    index_1++;
                }
                else
                {
                    index_2++;
                }
            }
            else if(index_1 != size_1 &&index_2 == size_2)
            {
                index_1++;
            }
            else if(index_1 == size_1 && index_2 != size_2)
            {
                index_2++;
            }
        }
        double sum = 0;
        for(int i = 0; i < calculate_times; i++)
        {
            if(index_1 != size_1 && index_2 != size_2)
            {
                if(nums1[index_1] < nums2[index_2])
                {
                    sum += nums1[index_1++];
                }
                else
                {
                    sum += nums2[index_2++];
                }
            }
            else if(index_1 != size_1 && index_2 == size_2)
            {
                sum += nums1[index_1++];
            }
            else if(index_1 == size_1 && index_2 != size_2)
            {
                sum += nums2[index_2++];
                
            }
        }
        return sum/calculate_times;
    }
};

运行结果：36ms，超过66.4%