力扣困难难度 第4题 寻找两个正序数组的中位数

标签: 力扣刷题  leetcode

先看一眼题
在这里插入图片描述

我的思路:
设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。
·每次比较nums[i]nums[j],如果前者小则i++,否则j++
·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以输出中位数的时候,要仔细思考中位数在哪个位置(详情请看代码中的下标判断位置)]否则说明循环是被中断的。循环被中断意味着nums1或者nums2中有一个数组已经遍历完了,中位数应该到另一个数组中去寻找。
·当要输出中位数的时候,不论以上哪种情况,均要讨论length是奇数还是偶数的情况,奇数的情况则直接输出中位数,偶数的话需要输出 (中位数+中位数前面那个数)/2。

代码:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        if(length==1){
            try{
                return nums1[0];
            }catch (Exception e){
                return nums2[0];
            }
        }
        if (nums1.length == 0) {
            int count;
            for (count = 0; count < nums2.length / 2; count++)
                ;
            if (length % 2 != 0)
                return nums2[count];
            else
                return (double) (nums2[count] + nums2[count - 1]) / 2;
        }
        if (nums2.length == 0) {
            int count;
            for (count = 0; count < nums1.length / 2; count++)
                ;
            if (length % 2 != 0)
                return nums1[count];
            else
                return (double) (nums1[count] + nums1[count - 1]) / 2;
        }
        boolean jishu = false;
        if (length % 2 != 0)
            jishu = true;
        int count = 0;
        int i = 0, j = 0;
        int k = -1;//k==0代表最后一次是i自增了,k==1代表最后一次是j自增了
        while (count < length / 2) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    i++;
                    count++;
                    k=0;
                } else {
                    j++;
                    count++;
                    k=1;
                }
            }
            if (i == nums1.length || j == nums2.length)
                break;
        }
        if (count == length / 2) {
            //正好有一个数组被遍历完的同时,找到了第count个数
            if (i == nums1.length) {
                if (jishu){
                    if(k==0)
                        return nums1[i-1]<nums2[j]?nums2[j]:nums1[i-1];
                    else
                        return nums2[j-1]<nums1[i]?nums1[i]:nums2[j-1];
                }
                else
                    return (double) (nums1[i-1] + nums2[j]) / 2;
            }else if(j==nums2.length){
                if (jishu)
                    if(k==0)
                        return nums1[i-1]<nums2[j]?nums2[j]:nums1[i-1];
                    else
                        return nums2[j-1]<nums1[i]?nums1[i]:nums2[j-1];
                else
                    return (double) (nums1[i] + nums2[j-1]) / 2;
            }
            if (jishu)
                return nums1[i] < nums2[j] ? nums1[i] : nums2[j];
            else {
                int a = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
                if(k==0)
                    i--;
                if(k==1)
                    j--;
                int b = nums1[i] < nums2[j] ? nums1[i] : nums2[j];
                return (double) (a + b) / 2;
            }
        }
        //因为一个数组率先结束而终止循环的情况
        if (i == nums1.length) {
            while (count < length / 2) {
                j++;
                count++;
            }
            if (jishu)
                return nums2[j];
            else return (double) (nums2[j] + nums2[j-1]) / 2;
        }
        while (count < length / 2) {
            i++;
            count++;
        }
        if (jishu)
            return nums1[i];
        else return (double) (nums1[i] + nums1[i - 1]) / 2;
    }
版权声明:本文为qq_38041237原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38041237/article/details/109459074

智能推荐

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

猜你喜欢

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...

OpenStack代码贡献初体验

为什么80%的码农都做不了架构师?>>>     OpenStack如今已成为开源云平台中的明星项目,得到广泛关注。OpenStack的优秀出众依赖于众多开发者的努力,在享受其带来的便利与快捷的同时,为其做一份贡献也是一个开发者的义务。  在前段时间的OpenStack的测试过程中,我发现Nova项目中的一个Bug,于是向社区提交了Bug报...