您现在的位置是:首页 > 正文

【解题笔记】leetcode寻找两个正序数组的中位数

2024-01-30 23:14:11阅读 0

问题转化

首先,考虑只有一个有序数组的情况:寻找中位数的问题可以转化为寻找一条分割线,满足以下两个条件:

  • 这条分割线在数组元素个素为奇数的时候,分割线左边的元素比右边多一个,中位数就是分割线左边的元素。
  • 数组元素个数为偶数的时候,分割线左边的元素与右边的元素一样多。中位数是分割线左右两个元素的平均值。

下面考虑两个有序数组,我们可以在两个数组上都划分一条分割线,这两条分割线有以下两个条件 :

  • 两条分割线左边的元素个数 = 两条分割线右边的元素个数
  • 两条分割线左边的元素均小于右边的元素
    此时,这道题就从寻找中位数转化为了寻找满足上述两个条件的分割线。题目要求时间复杂度为O(log (m+n)),因此能够直接联想到使用二分查找法来找分割线。

解题步骤

寻找满足上述两个条件的分割线,那么我们就围绕上述两个条件来编码:为了描述方便,将nums1设置为长度较短的数组,nums2设置为长度较长的数组。

第一个条件:

要考虑奇数和偶数的情况,如果两个数组长度之和为奇数,那么我们就规定左边元素比右边元素多;如果两个数组长度之和为偶数,那么两边元素相等。由于Java的除法是向下取整(即5/2=2),因此可以讲奇偶两种情况合并,得到左边元素的总个数
t o t a l L e f t = m + n + 1 2          / / 其 中 m , n 分 别 代 表 两 个 数 组 的 长 度 totalLeft = \frac{m+n+1}{2}~~~~~~~~//其中m,n分别代表两个数组的长度 totalLeft=2m+n+1        //mn

第二个条件:

要使分割线左边元素均小于右边的元素,因为两个数组均为有序数组,那么满足以下条件即可:
i为nums1分割线右边的元素,j为nums2分割线右边的元素。

nums1[i-1]<=nums2[j] && nums2[j-1]<=nums1[i]

根据上述两个条件编码:

  • 据此,根据第一个条件,我们可以知道ij的等量关系,即i+j=totalLeft。知道这个等量关系以后就很好办了,我们每次只需要移动i,让j=totalLeft-i即可。

  • 根据第二个条件,我们只需要比较nums1[i-1]nums2[j]的大小关系即可。如果前者大,说明分割线太靠右了;反之,继续向右寻找看还有没有满足条件的。
    如下图:此时i指向元素2,j指向元素4。1<4,因此nums1的分割线右移。由j=totalLeft-i得,nums2的分割线左移。

image-20220319101709876
二分查找法编码:

//第一步:将长度最短的数组设置为nums1
if (nums2.length < nums1.length) {
  int[] temp = nums1;
  nums1 = nums2;
  nums2 = temp;
}


//第二步:设置分割线左边元素的个数
int m = nums1.length;
int n = nums2.length;
int totalLeft = (m + n + 1) / 2; //合并奇数和偶数的情况


//第三步,设置left与right,代表nums1分割线的查找区间。注:right需要设置为nums1.length,因为i可以为nums1.length,此时分割线就在nums1的最右边
int left = 0;
int right = nums1.length;

/*两个条件:
        1. 分隔线左边的元素个数等于分隔线右边的元素个素
        2. 分隔线左边的所有元素均小于分隔线右边的元素个素
        即nums1[i-1] <= nums2[j] && nums2[j-1] <= num1[i]

        注:i是nums1分割线右边的第一个元素,它的下标 = 分隔线左边元素的个数;
        j同理,因此: i + j = totalLeft,可以根据该表达式,由i确定j。
        */
while (left < right) {
  int i = left + (right - left + 1) / 2;
  int j = totalLeft - i;
  if (nums1[i - 1] > nums2[j]) {
    //说明nums1的分隔线太靠右了,需要在[left,i-1处继续寻找]
    right = i - 1;
  } else {
    //需要在[i,right]处继续寻找
    left = i;
  }
}

//第四步:分割线划分完毕,确定两个数组分割线右边的位置i,j。此时left所指向的元素是nums1分割线右边的元素
int i = left;
int j = totalLeft - i;

极端情况:

下面讨论四种分割线划分的极端情况,仅以两种情况举例说明

  • nums1的分割线在数组最左边
    image-20220319110159313

    • 因为nums1分隔线左边没有元素,因此可以得出两个数组分割线左边的最大值肯定在nums2中。
    • 此时要把nums1[i-1]设置为无限小的值,使得最后选择左边元素最大值的时候不要选中它。
  • nums1的分割线在数组最右边
    image-20220319110136556

    • 因为nums1分隔线右边没有元素,因此可以得出两个数组分割线右边的最小值肯定在nums2中。
    • 此时要把nums1[i]设置为无限大的值,使得最后选择右边元素最小值的时候不要选中它。
  • nums2的分割线在数组最左边

  • nums2的分割线在数组最左边
    因此,考虑到四种极端情况,要在获得中位数前加上以下代码:

int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
//此时nums1分割线左边没有元素了,因此nums1分割线左边元素的最大值要设置成无限小,在比较时直接选中nums2分割线的左边元素,其余同理
int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

得到中位数

分割线划分完毕后,即可求得中位数:

  • 数组长度和为奇数:两条分割线左边元素的最大值
  • 数组长度和为偶数:两条分割线左边元素最大值与右边元素最小值的平均值
//最后一步:中位数
if ((m + n) % 2 == 0) {
  //偶数
  return (double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
}
return Math.max(nums1LeftMax, nums2LeftMax);

注意

在写二分查找法时,如果查找到右区间时使用left=middle的方式编码,那么需要注意避免死循环的情况。
比如某个区间只有两个数[i,j],如果left=iright=j,那么若中间值一直不动,就会陷入死循环。因此确定中间值的时候应该使用left + (right - left + 1) / 2,这样就能保证如果二分查找查到了右区间,左边界加一。详情可见代码

完整代码

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {

    //第一步:将长度最短的数组设置为nums1
    if (nums2.length < nums1.length) {
      int[] temp = nums1;
      nums1 = nums2;
      nums2 = temp;
    }


    //第二步:设置分割线左边元素的个数
    int m = nums1.length;
    int n = nums2.length;
    int totalLeft = (m + n + 1) / 2; //合并奇数和偶数的情况


    //第三步,设置left与right,代表nums1分割线的查找区间。注:right需要设置为nums1.length,因为i可以为nums1.length,此时分割线就在nums1的最右边
    int left = 0;
    int right = nums1.length;

    /*两个条件:
        1. 分隔线左边的元素个数等于分隔线右边的元素个素
        2. 分隔线左边的所有元素均小于分隔线右边的元素个素
        即nums1[i-1] <= nums2[j] && nums2[j-1] <= num1[i]

        注:i是nums1分割线右边的第一个元素,它的下标 = 分隔线左边元素的个数;
        j同理,因此: i + j = totalLeft,可以根据该表达式,由i确定j。
        */
    while (left < right) {
      int i = left + (right - left + 1) / 2;
      int j = totalLeft - i;
      if (nums1[i - 1] > nums2[j]) {
        //说明nums1的分隔线太靠右了,需要在[left,i-1处继续寻找]
        right = i - 1;
      } else {
        //需要在[i,right]处继续寻找
        left = i;
      }
    }
    //第四步:分割线划分完毕,确定两个数组分割线右边的位置i,j。此时left所指向的元素是nums1分割线右边的元素
    int i = left;
    int j = totalLeft - i;

    //第五步:确定中位数,无论是奇数还是偶数,中位数都只与两个数组分割线左边元素的最大值x 和 右边元素的最小值y 有关。
    //因为设定分割线左边元素等于右边元素,或大于一,因此中位数=x 或中位数=(x+y)/2
    int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
    //此时nums1分割线左边没有元素了,因此nums1分割线左边元素的最大值要设置成无限小,在比较时直接选中nums2分割线的左边元素,其余同理
    int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
    int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
    int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

    //最后一步:中位数
    if ((m + n) % 2 == 0) {
      //偶数
      return (double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
    }
    return Math.max(nums1LeftMax, nums2LeftMax);
  }
}

网站文章

  • 记chrome打不开网址,无法搜索问题

    下载插件,解压后拖入chrome的扩展程序中,可以打开国内网址。

    2024-01-30 23:14:04
  • PHP不用临时变量, 怎么交换两个整数变量的值. 譬如$a=2 $b=3使用第三个变量交换他们的值

    如果能用第三个变量那么问题就很简单了$a=2; $b=3; $c=$a; $b=$a; $a=$c;搞定现在不允许有$c, 那可咋整呢方案一 用数组$a=2;$b=3;$a=[$a, $b];$b=...

    2024-01-30 23:13:35
  • CSS属性总结(三):positioning, dimension, list, table

    CSS属性总结(三):positioning, dimension, list, table

    定位 position 设置元素的定位类型,相当于声明当前元素的布局所使用的定位机制,需要left、top、right、bottom、z-index等属性配合使用,否则没有实际效果。取值如下表所示: top、bottom、left、right 设置元素的上/下/左/右外边距的边缘与包含该元素的上/下/左/右边界之间的偏移。取值可以是auto,表示浏览器自动计算距离;也可以是带单位的...

    2024-01-30 23:13:27
  • Flink读取HDFS上的Parquet文件生成DataSet

    首先打开Flink的官方网站,查看一下DataSet已支持的数据源。 File-based readTextFile(path) / TextInputFormat - Reads files line wise and returns them as Strings. readTextFileWithValue(path) / TextValueInputFormat - Reads fi...

    2024-01-30 23:13:21
  • Python 文件操作

    python中对文件、文件夹(文件操作函数)的操作需要涉及到os模块和shutil模块。得到当前工作目录,即当前Python脚本工作的目录路径: os.getcwd()返回指定目录下的所有文件和目录名:os.listdir()函数用来删除一个文件:os.remove()删除多个目录:os.removedirs(r“c:\python”)检验给出的

    2024-01-30 23:13:15
  • Python代码编写规范

    Python代码编写规范

    Python代码编写规范

    2024-01-30 23:12:47
  • Java开发琐碎语法(长期更新)

    1、List赋初值可使用:Arrays.asList(0.1, 0.25, 0.5, 0.75, 0.9);3、BigDecimal的加减乘除:add、subtract、multiply、divide...

    2024-01-30 23:12:42
  • 简单的打字游戏心得体会(代码)

    生成字母: Ø 可以用label ,span等标签将字母包里面,因为这些标签的范围正好是标签内的文本的大小,而,div或者p标签则会使整行的区域都包括,需要设置样式,所以在这选择的是label。var...

    2024-01-30 23:12:35
  • 服务器阻止了对组件 ad,解决SQL Server 阻止了对组件Ad Hoc Distributed Queries访问的方法...

    服务器阻止了对组件 ad,解决SQL Server 阻止了对组件Ad Hoc Distributed Queries访问的方法...

    今天单位一ASP.NET网站,里面有个功能是导出数据,发现一导出就报错,报错内容是:SQL Server 阻止了对组件 'Ad Hoc Distributed Queries' 的 STATEMENT'OpenRowset/OpenDatasource' 的访问,因为此组件已作为此服务器安全配置的一部分而被关闭。系统管理员可以通过使用 sp_configure 启用 'Ad Hoc Dis...

    2024-01-30 23:12:04
  • 运维体系管理16-线上环境建设,要扛得住真刀真枪的考验

    运维体系管理16-线上环境建设,要扛得住真刀真枪的考验

    我们简单构建一张模型图来对线上环境作个展示:我在这两期文章中介绍了这么多环境,我们可以看到,环境建设是一项异常繁琐复杂的工作,这些工作不是一蹴而就,而是根据实际的场景和问题催生出来的,所以是个逐步渐进...

    2024-01-30 23:11:56