【力扣 Hot100 | 第三天】4.12(寻找两个正序数组的中位数)

2024-04-12 20:52

本文主要是介绍【力扣 Hot100 | 第三天】4.12(寻找两个正序数组的中位数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

**【力扣 Hot100 | 第二天】4.11**

文章目录

  • 3.寻找两个正序数组的中位数
    • 3.1题目
    • 3.2解法:暴力(归并排序)
    • 3.3解法:二分法

3.寻找两个正序数组的中位数

3.1题目

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 O(log (m+n))

  • 示例一:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

3.2解法:暴力(归并排序)

  • 题目既然给出了两个正序数组,我们可以将这两个正序数组合成为一个正序的数组
  • 判断合成后的数组的长度为奇数还是偶数,进而求出中位数
  • 归并排序的时间复杂度为 O(m+n)、空间复杂度为 O(m+n)
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;// 合成的数组int[] res = new int[len1+len2];int index = 0;int left = 0, right = 0;// 归并排序合成部分while(left<len1&&right<len2) {if(nums1[left]<nums2[right]) {res[index++] = nums1[left++];} else {res[index++] = nums2[right++];}}// 判断nums1剩余还是nums2剩余,并将剩余部分加入到合成的数组之后while(left<len1) {res[index++] = nums1[left++];}while(right<len2) {res[index++] = nums2[right++];}// 判断合成后的数组的长度,求出中位数。返回的是double类型if((len1+len2)%2==1) {return (double) res[(len1+len2)/2];} else {return (double) (res[(len1+len2)/2]+res[(len1+len2)/2-1])/2;}}
}

3.3解法:二分法

  1. 暴力解法对于本题来说不满足时间复杂度,要求时间复杂度为O(log(m+n)),所以自然想到了二分法。

  2. 理解:

    1. 两个数组长度为奇数,则中位数即为第 (m+n)/2+1 小 元素;
    2. 两个数组长度为偶数,则中位数即为第 (m+n)/2 小元素 和 第 (m+n)/2+1 小元素;
  3. 归纳:如何求出两个数组中第k小的元素?

    1. 首先需要找到 第一个数组中的k/2位置、第二个数组的k/2位置;

    2. 如果 nums1[k/2] < nums2[k/2] ,则 nums1[k/2]及其前面的元素均不是第k小,所以我们应该从 nums1[k/2+1] 到末尾,以及nums2中查找

      1. why?

      2. 理由:比nums1[k/2]小的数字有 k/2-1个,比nums2[k/2]小的数字有 k/2-1个;

        又又 nums1[k/2] < nums2[k/2]

        即 比nums2[k/2]小的数字最小有 (k/2-1)+(k/2-1)+1= k-1个

        即nums1[k/2]最多是第k-1个数,它及其前面的肯定不是第k个数,所以需要去掉

    3. 如果 nums1[k/2] > nums2[k/2],则 nums2[k/2]及其后面的元素均不是第k小,所以我们应该从 nums1 以及 nums2[k/2+1]到末尾中查找

  4. 例子:

    image-20240412170933717

public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int left = (n + m + 1) / 2;int right = (n + m + 2) / 2;//将偶数和奇数的情况合并,如果是奇数,会求两次同样的 k 。return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;//让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);if (len1 == 0) return nums2[start2 + k - 1];if (k == 1) return Math.min(nums1[start1], nums2[start2]);int i = start1 + Math.min(len1, k / 2) - 1;int j = start2 + Math.min(len2, k / 2) - 1;if (nums1[i] > nums2[j]) {return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));}else {return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));}
}

在这里插入图片描述

这篇关于【力扣 Hot100 | 第三天】4.12(寻找两个正序数组的中位数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/898211

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的