• 【LeetCode】寻找两个正序数组的中位数 [H]（二分法）

    4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

    一、题目

    给定两个大小分别为 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

    二、代码

    1. class Solution {
    2.     public  double findMedianSortedArrays(int[] nums1, int[] nums2) {
    3.         // 记录两个数组的总长度
    4.         int size = nums1.length + nums2.length;
    5.         // 标记总长度是奇数还是偶数
    6.         boolean isEven = (size & 1) == 1 ? false : true;
    7.  
    8.         // 如果两个数组都不为空
    9.         if (nums1 != null && nums1.length > 0 && nums2 != null && nums2.length > 0) {
    10.             // 总长度的中间位置
    11.             int mid = size / 2;
    12.             // 如果总长度是偶数，那么要返回的中位数就是上中位数和下中位数相加除以2（两个数组排序合并之后的上中位数和下中位数）
    13.             if (isEven) {
    14.                 // 求第mid小和第mid+1小这两个数，然后相加除以2
    15.                 return (findKthNum(nums1, nums2, mid) + findKthNum(nums1, nums2, mid + 1)) / 2.0;
    16.             // 如果总长度是奇数，那么要返回的中位数就是第mid个数
    17.             } else {
    18.                 // 求第mid+1小这个数
    19.                 return findKthNum(nums1, nums2, mid + 1);
    20.             }
    21.         // 只有nums2不为空
    22.         } else if (nums1 == null || nums1.length == 0) {
    23.             // 如果nums2长度为偶数
    24.             if (isEven) {
    25.                 // 因为nums2本身就是有序的，直接求其中位数即可
    26.                 // 注意位移运算符的优先级比较弱，所以它的计算要括上括号
    27.                 int mid = (nums2.length >> 1) - 1;
    28.                 return (nums2[mid] + nums2[mid + 1]) / 2.0;
    29.             // 如果nums2长度为奇数
    30.             } else {
    31.                 // 可直接算中位数
    32.                 int mid = nums2.length >> 1;
    33.                 return nums2[mid];
    34.             }
    35.         // 只有nums1不为空   同上一个分支
    36.         } else if (nums2 == null || nums2.length == 0) {
    37.             if (isEven) {
    38.                 int mid = (nums1.length >> 1) - 1;
    39.                 return (nums1[mid] + nums1[mid + 1]) / 2.0;
    40.             } else {
    41.                 int mid = nums1.length >> 1;
    42.                 return nums1[mid];
    43.             }
    44.         // 这个分支其实没用，只是为了有个返回值而已，避免报错
    45.         } else {
    46.             return 0;
    47.         }
    48.     }
    49.  
    50.     // 在两个都有序的数组中，找整体第kth小的数，两个数组不等长
    51. 	// 可以做到O(log(Min(M,N)))
    52.     // 注意这里传入的kth是第kth小，并不是下标
    53.     public  int findKthNum(int[] nums1, int[] nums2, int kth) {
    54.         // 标记处短数组和长数组   注意这里要有一个写上等号，保证shorts和longs数组一定指向的是不同的数组
    55.         int[] shorts = nums1.length <= nums2.length ? nums1 : nums2;
    56.         int[] longs = nums1.length > nums2.length ? nums1 : nums2;
    57.         int shortsLen = shorts.length;
    58.         int longsLen = longs.length;
    59.  
    60.         // 如果kth小于shortsLen
    61.         if (kth <= shortsLen) {
    62.             // 那么在长数组中切除和短数组等长的前缀树组，两个等长数组求上中位数，就是答案。
    63.             // 传入的两个数组长度相等，直接调用算法原型
    64.             return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
    65.         // 如果kth大于shortsLen小于等于longsLen
    66.         } else if (kth > shortsLen && kth <= longsLen) {
    67.             // 先找到要排除长数组哪些位置的数
    68.             int preIndex = kth - shortsLen - 1;
    69.             int posIndex = kth - 1;
    70.             // 单独判断longs[preIndex]和shorts[shortsLen - 1]
    71.             if (longs[preIndex] >= shorts[shortsLen - 1]) {
    72.                 return longs[preIndex];
    73.             // 如果不满足上面的条件，就说明longs[preIndex]不可能是第kth小的数，直接抛弃，那么传入的两个数组长度就又相等了，直接调用算法原型
    74.             } else {
    75.                 return getUpMedian(shorts, 0, shortsLen - 1, longs, preIndex + 1, posIndex);
    76.             }
    77.         // 如果kth大于longsLen
    78.         } else {
    79.             // 先找到段数组和长数组要排除的位置
    80.             int longIndex = kth - shortsLen - 1;
    81.             int shortIndex = kth - longsLen - 1;
    82.  
    83.             // 单独判断longs[longIndex]和shorts[shortsLen - 1]
    84.             if (longs[longIndex] >= shorts[shortsLen - 1]) {
    85.                 return longs[longIndex];
    86.             // 单独判断shorts[shortIndex]和longs[longsLen - 1]
    87.             } else if (shorts[shortIndex] >= longs[longsLen - 1]) {
    88.                 return shorts[shortIndex];
    89.             }
    90.             // 舍弃掉一个不可能的数之后，传入的两个数组长度就相等了，调算法原型
    91.             return getUpMedian(shorts, shortIndex + 1, shortsLen - 1, longs, longIndex + 1, longsLen - 1);
    92.         }
    93.     }
    94.  
    95. 	// nums1[s1...e1]
    96. 	// nums2[s2...e2]
    97. 	// 一定等长！
    98. 	// 返回整体的，上中位数
    99.     public int getUpMedian(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2) {
    100.         // 整个代码很好理解，可以在纸上列一个具体的例子，就很容易写出这个代码
    101.         while (s1 < e1) {
    102.             int mid1 = (s1 + e1) >> 1;
    103.             int mid2 = (s2 + e2) >> 1;
    104.  
    105.             if (nums1[mid1] == nums2[mid2]) {
    106.                 return nums1[mid1];
    107.             }
    108.             // 执行到这里说明两个中点一定不等！
    109. 			// 奇数长度
    110.             if ((e1 - s1 + 1) % 2 == 1) {
    111.                 if (nums1[mid1] > nums2[mid2]) {
    112.                     if (nums2[mid2] >= nums1[mid1 - 1]) {
    113.                         return nums2[mid2];
    114.                     }
    115.                     e1 = mid1 - 1;
    116.                     s2 = mid2 + 1;
    117.                 } else {
    118.                     if (nums2[mid2 - 1] <= nums1[mid1]) {
    119.                         return nums1[mid1];
    120.                     }
    121.                     e2 = mid2 - 1;
    122.                     s1 = mid1 + 1;
    123.                 }
    124.             // 偶数长度
    125.             } else {
    126.                 if (nums1[mid1] > nums2[mid2]) {
    127.                     e1 = mid1;
    128.                     s2 = mid2 + 1;
    129.                 } else {
    130.                     e2 = mid2;
    131.                     s1 = mid1 + 1;
    132.                 }
    133.             }
    134.         }
    135.         // 跳出上面循环后，只剩下两个数了，小的那个数就是上中位数。我感觉上面这个过程就和二分有点类似
    136.         return Math.min(nums1[s1], nums2[s2]);
    137.     }
    138. }

    三、解题思路 

    一看到有序，就要想到利用二分的思路，将数据规模减半，基于一个算法模型可以求出任意第k个数组，既然也就可以求中位数。整个时间复杂度是O(log(Min(M,N)))。

  • 相关阅读:
    Session会话追踪的实现机制
    spark内置数据类型
    在线客服系统品牌排行榜
    050：vue+openlayers使用Popup组件显示经纬度坐标（代码示例）
    SSRF漏洞
    神经网络一般训练多少次,神经网络训练时间过长
    详解SpringBoot的核心特性
    ComText让机器人有了情节记忆
    安装docker ，更换docker版本
    Xilinx SDK编译完成自动生成SREC文件（适用于ISE、Vivado、Vitis）
  • 原文地址：https://blog.csdn.net/cy973071263/article/details/127593593