两个排序数组的中值-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

**难度: Hard**

> 内容描述

```
有两个大小分别为m和n的排序数组nums1和nums2。
求两个排序数组的中值。总体运行时复杂性应该是O（log（m+n））。
您可以假设nums1和nums2不能同时为空。

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

```

## 解题方案

> 思路 1
******- 时间复杂度: O(log(m + n))******- 空间复杂度: O(1)******

将问题转化为两个有序数组，找出其中的第K大的数, beats 99.80%

```java
class Solution {
// 寻找两个有序数组的中位数
    // 问题转换为求第K大的数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0){
            // 求nums2的中位数
            return nums2.length % 2 == 0 ? (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0 : nums2[nums2.length / 2];
        }
        if(nums2 == null || nums2.length == 0){
            return nums1.length % 2 == 0 ? (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) / 2.0 : nums1[nums1.length / 2];
        }
        int len = nums1.length + nums2.length;
        return len % 2 == 0 ? (topK(nums1,nums2,0,0,len/2)+topK(nums1,nums2,0,0,len/2+1))/2.0 : topK(nums1,nums2,0,0,len/2 + 1);
    }
    // 找两个有序数组的topk小的数
    public int topK(int[] nums1,int[] nums2,int start1,int start2,int k){
        if(start1 >= nums1.length){
            return nums2[start2 + k - 1];
        }
        if(start2 >= nums2.length){
            return nums1[start1 + k - 1];
        }

if(k == 1){
            return Math.min(nums1[start1] , nums2[start2]);
        }

if(start1 + k / 2 > nums1.length){ // 肯定不会在nums2的前 k / 2
            return topK(nums1,nums2,start1,start2 + k / 2,k - k / 2);
        }else if(start2 + k / 2 > nums2.length){
            return topK(nums1,nums2,start1 + k / 2,start2,k - k / 2);
        }

int mid1 = nums1[start1 + k / 2 - 1];
        int mid2 = nums2[start2 + k / 2 - 1];
        if(mid1 > mid2){ // 移除nums2的前k/2
            return topK(nums1,nums2,start1,start2 + k / 2,k - k / 2);
        }else {
            return topK(nums1,nums2,start1 + k / 2,start2,k - k/2);
        }
    }
}
```

该分类下的相关小册推荐：

数据结构与算法之美

数据结构与算法(下)

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法(上)

算法面试通关 50 讲

编程之道-算法面试(上)