草庐IT

leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)

okokabcd 2023-03-28 原文

一、题目大意

标签: 查找

https://leetcode.cn/problems/median-of-two-sorted-arrays

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

二、解题思路

号称leetcode守门员的题。中位数可以来自于同一个数组，也可以来自于两个数组，可以是一个数，也可以是两个数。
实现思路（参考花花酱的讲解）
分类：

思路：假设n1,n2是两个数组的元素，那么k=(n1+n2+1)/2就表示左中位数或中位数的索引，假设从nums1中取m1个元素，从nums2中取m2个元素，那么m1+m2 = k。我们要求的中位数就是从max(nums[m1-1], nums[m2-1])和min(nums[m1], nums[m2])。

三、解题方法

3.1 Java实现

public class Solution2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        // 对长度小的数组做二分搜索
        if (n1 > n2 ) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 偶数情况：nums1=>[1, 2, 3] nums2=>[3, 4, 5]  中位数 2 3
        // 奇数情况：nums1=>[1, 2, 3] nums2=>[2, 3, 4, 5] 中位数 3
        // nums1=>[-1, 1, 3, 5, 7, 9] nums2=>[2, 4, 6, 8, 10, 12, 14, 16]
        int l = 0;
        int r = n1;
        // 偶数情况：左中位数 奇数情况：中位数
        int k = (n1 + n2 + 1) / 2;
        while (l < r) {
            int m1 = l + (r - l) / 2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2-1]) {
                l = m1 + 1;
            } else {
                r = m1;
            }
        }
        int m1 = l;
        int m2 = k - l;

        int c1 = Math.max(m1 < 1 ? Integer.MIN_VALUE : nums1[m1-1], m2 < 1 ? Integer.MIN_VALUE : nums2[m2-1]);
        // 奇数情况
        if ((n1 + n2) % 2 == 1) {
            return c1;
        }

        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
}

四、总结小记

  • 2022/5/30 做不出来的题就参考别人的吧，再转为自己的思路吧
leetcodeMediannumsnums1nums2算法与数据结构

有关leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  3. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  4. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  5. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  6. arrays - 如何在下面的示例中将两个值数组分组为 n 个值数组？ - 2

    我已经有很多两个值数组，例如下面的例子ary=[[1,2],[2,3],[1,3],[4,5],[5,6],[4,7],[7,8],[4,8]]我想把它们分组到[1,2,3],[4,5],[5,6],[4,7,8]因为意思是1和2有关系，2和3有关系，1和3有关系，所以1,2,3都有关系我如何通过ruby​​库或任何算法来做到这一点？ 最佳答案 这是基本Bron–Kerboschalgorithm的Ruby实现:classGraphdefinitialize(edges)@edges=edgesenddeffind_maximum_

  7. ruby - 尝试比较两个文本文件，并根据信息创建第三个 - 2

    我有两个文本文件，master.txt和926.txt。如果926.txt中有一行不在master.txt中，我想写入一个新文件notinbook.txt。我写了我能想到的最好的东西，但考虑到我是一个糟糕的/新手程序员，它失败了。这是我的东西g=File.new("notinbook.txt","w")File.open("926.txt","r")do|f|while(line=f.gets)x=line.chompifFile.open("master.txt","w")do|h|endwhile(line=h.gets)ifline.chomp!=xputslineendende

  8. ruby - 在两个 ActiveRecord 类之间合并/复制属性的好方法？ - 2

    之前有人问过这个问题，我发现了以下clip关于如何一次设置一个类对象的所有属性，但由于批量分配保护，这在Rails中是不可能的。(例如，您不能Object.attributes={})有没有一种很好的方法可以将一个类的属性合并到另一个类中？object1.attributes=object2.attributes.inject({}){|h,(k,v)|h[k]=vifObjectModel.column_names.include?(k);h}谢谢。 最佳答案 利用assign_attributes使用:without_prote

  9. ruby-on-rails - ruby 中两个哈希之间的变化 - 2

    我有两个具有以下格式的哈希mydetails[x['Id']]=x['Amount']这将包含如下数据hash1={"A"=>"0","B"=>"1","C"=>"0","F"=>"1"}hash2={"A"=>"0","B"=>"3","C"=>"0","E"=>"1"}我期待这样的输出:Differencesinhash:"B,F,E"非常感谢任何帮助。 最佳答案 这个解决方案可能更容易理解:(hash1.keys|hash2.keys).select{|key|hash1[key]!=hash2[key]}Array#|返回2

  10. ruby-on-rails - 为什么用户必须输入 7 位数的 Twitter PIN 才能授予我的应用程序访问权限？ - 2

    我正在为我的用户实现一些ruby​​onrails代码推特内容。我正在创建正确的oauth链接...类似http://twitter.com/oauth/authorize?oauth_token=y2RkuftYAEkbEuIF7zKMuzWN30O2XxM8U9j0egtzKv但在我的测试帐户授予对twitter的访问权限后，它会弹出一个页面，上面写着“您已成功授予对.我不知道用户应该在哪里输入此PIN以及他们为什么必须这样做。我认为这不是必要的步骤。Twitter应该将用户重定向到我在应用程序设置中提供的回调URL。有谁知道为什么会这样？更新我找到了thisarticle声明我需

随机推荐