LeetCode-4 寻找两个有序数组的中位数

Leefs 2020-02-19 AM 3175℃ 0条

# LeetCode-4 寻找两个有序数组的中位数

题目描述

```
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。
```

示例 1:

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

则中位数是 2.0
示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

**代码实现**

```java
public class Solution04 {
    public static void main(String[] args) {
        int[] arr1={1,5};
        int[] arr2={3};
        double v = findMedianSortedArrays(arr1, arr2);
        System.out.println(v);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

int len = nums1.length + nums2.length;
        double Median = 0;

int i = 0;
        int count = 0;
        int a = 0;//指向nums1数组的角标
        int b = 0;  //指向nums2数组的角标
        int[] num3 = new int[len];//用来存放有序的 nums1数组和mums2数组
        while (i < len) {
            if (a < nums1.length && b < nums2.length) {   //两数组都未遍历完，相互比较后加入
                if (nums1[a] > nums2[b]) {
                    num3[i] = nums2[b];
                    b++;
                    count++;
                } else {
                    num3[i] = nums1[a];
                    a++;
                    count++;
                }
            } else if (a < nums1.length) {   //num2已经遍历完，无需比较，直接将剩余num1加入
                num3[i] = nums1[a];
                a++;
                count++;
            } else if (b < nums2.length) {    //num1已经遍历完，无需比较，直接将剩余num2加入
                num3[i] = nums2[b];
                b++;
                count++;
            }
            if(count == len /2 +1 ) break;//找到中间+1位置后停止查找
            i++;
        }
        if(len % 2 == 0){
            double d1 = num3[i];
            double d2 = num3[i-1];
            Median = (d1 + d2)/2;
        } else{
            Median = num3[i];
        }
        return Median;

}
}
```

> 运行结果

```
3.0
```

标签: LeetCode刷题

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/632.html

上一篇【转载】volatile关键字简介

下一篇【转载】单例模式简介

LeetCode-4 寻找两个有序数组的中位数

评论啦~

栏目分类

标签云

友情链接申请

LeetCode-4 寻找两个有序数组的中位数

 评论啦~

 栏目分类

标签云

友情链接申请

评论啦~

栏目分类

标签云

友情链接申请