数组-在两个长度相等的有序数组中找到上中位数

2024-05-25 19:04

本文主要是介绍数组-在两个长度相等的有序数组中找到上中位数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

解题思路

此题目直接遍历两个列表,时间复杂度为O(n);使用二分法去比较两个递增列表的中位数,缩小两个数组中位数范围,时间复杂度O(logn),这里我们的算法实现使用二分法。

通过举例子来说明解题算法:

在循环过程中,每时每刻都保持两个比较列表的长度是相等的

1.当两个列表 [low1,high1] [low2,high2] 的中位数相等时:

        [1,3,4,5]和[2,3,5,6]=[1,2,3,3,4,5,5,6]

        [1,4,5,6,7]和[2,3,5,7,8]=[1,2,3,4,5,5,6,7,7,8]

可以看到,无论(high1-low1+1)是奇数还是偶数,当arr[mid]相等时,上中位数就是arr[mid]

2.当两个列表 [low1,high1] [low2,high2] 的中位数arr1[mid1]<arr2[mid2]时:

        当(high1-low1+1)是奇数时:[1,2,4,8,9] 和 [2,3,5,7,9]  low1=mid1;high2 = mid2;

        当(high1-low1+1)是偶数时:[1,2,4,8] 和 [2,3,4,7]        low1=mid1+1;high2 = mid2;

        缩小范围到黄色加粗内。

3.当两个列表 [low1,high1] [low2,high2] 的中位数arr1[mid1]>arr2[mid2]时:

        当(high1-low1+1)是奇数时:[1,5,7,8,9] 和 [2,3,5,7,9]  low2=mid2;high1 = mid1;

        当(high1-low1+1)是偶数时:[1,5,7,8] 和 [2,3,4,7]        low2=mid2+1;high1 = mid1;

        缩小范围到黄色加粗内。

4.最后返回arr1[low1]和arr2[low2]中的较小者。

代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** find median in two sorted array* @param arr1 int整型一维数组 the array1* @param arr2 int整型一维数组 the array2* @return int整型*///这里直接遍历两个列表,时间复杂度为O(n)//使用二分法去比较两个递增列表的中位数,缩小两个数组中位数范围,时间复杂度O(logn)public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {// 这里使用二分法int res = 0;int low1 = 0, high1 = arr1.length - 1;int low2 = 0, high2 = arr2.length - 1;while (low1 < high1) {int mid1 = (low1 + high1) / 2;int mid2 = (low2 + high2) / 2;if (arr1[mid1] == arr2[mid2]) {//这个不管是奇数还是偶数都成立://[1,3,4,5]和[2,3,5,6]=[1,2,3,3,4,5,5,6]//[1,4,5,6,7]和[2,3,5,7,8]=[1,2,3,4,5,5,6,7,7,8]low1 = mid1;low2 = mid2;break;} else if (arr1[mid1] < arr2[mid2]) {if ((high1 - low1 + 1) % 2 == 1) { //如果high1-low1+1为奇数//比如[1,2,4,8,9]和[2,3,5,7,9]low1 = mid1;high2 = mid2;} else { //如果high1-low1+1为偶数//比如[1,2,4,8]和[2,3,4,7]low1 = mid1 + 1;high2 = mid2;}} else {if ((high1 - low1 + 1) % 2 == 1) { //如果high1-low1+1为奇数//比如[1,5,7,8,9]和[2,3,5,7,9]low2 = mid2;high1 = mid1;} else { //如果high1-low1+1为偶数//比如[1,5,7,8]和[2,3,4,7]high1 = mid1;low2 = mid2 + 1;}}}res = arr1[low1] < arr2[low2] ? arr1[low1] : arr2[low2];return res;}
}

刷题链接

在两个长度相等的排序数组中找到上中位数_牛客题霸_牛客网

这篇关于数组-在两个长度相等的有序数组中找到上中位数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1002361

相关文章

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 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

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

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

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

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

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

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

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