刷脸支付 element SQLMAP 劝酒文化 excel caching model bootstrap管理模板 nodejs后端开发 mysql学习 安装mysql python集合 python开发工具 java的substring java替换字符串 获取当前时间java linux密码 atq js闭包的理解 音乐狂app 一键隐藏 win10wifi 如何用ai设计字体 苹果手机不弹出信任 淘宝店铺采集 羽化快捷键 骰子表情包 lol修改皮肤 ae渲染设置 产品修图 换肤助手 chrome访问助手 ajax获取数据 数据库密码忘了怎么办 桌面cpu性能天梯图 打开mysql php队列 xp系统修复工具 方正倩体 php文件用什么打开
当前位置: 首页 > 学习教程  > 编程语言

Leetcode第四题

2020/8/11 19:15:45 文章标签:

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

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。 请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为
O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3] nums2= [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

暴力解题方法,一个while循环,每次弹出两个数组第一个数比较。
因为题中给的数组已经是正序排列好的,所以相对简单一点
是我一开始就想到的暴力解决办法,不符合O(log(m+n))的要求。

var findMedianSortedArrays = function(nums1, nums2) {
  let n = nums1.length + nums2.length
  let sum = n % 2 === 0 ? [n / 2 -1, n / 2] : Math.floor(n / 2)
  let temp = 0
  function arr(nums1,nums2){
    let a = 0
    if(nums1.length && nums2.length){
      a = nums1[0] <= nums2[0] ? nums1.shift() : nums2.shift()
    }else{
      nums1.length && (a = nums1.shift())
      nums2.length && (a = nums2.shift())
    }
    return a
  }
  while(nums1.length || nums2.length){
    let a = arr(nums1,nums2) 
    if(typeof(sum) === 'number' && temp === sum){
      return a
    }
    if(typeof(sum) === 'object' && temp === sum[0]){
      let b = arr(nums1,nums2)
      return (a + b)/2
    }
    ++temp
  }
};

时间复杂度:O(log(min(m, n)))O(log(min(m,n)))
空间复杂度:O(log(min(m, n)))O(log(min(m,n)))
二分解法

/**
 * 二分解法
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // make sure to do binary search for shorten array
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1]
  }
  const m = nums1.length
  const n = nums2.length
  let low = 0
  let high = m
  while(low <= high) {
    const i = low + Math.floor((high - low) / 2)
    const j = Math.floor((m + n + 1) / 2) - i

    const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
    const minRightA = i === m ? Infinity : nums1[i]
    const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
    const minRightB = j === n ? Infinity : nums2[j]

    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
      return (m + n) % 2 === 1
        ? Math.max(maxLeftA, maxLeftB)
        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    } else if (maxLeftA > minRightB) {
      high = i - 1
    } else {
      low = low + 1
    }
  }
};

参考自
作者:fe-lucifer
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/er-fen-fa-duo-yu-yan-javajs4-xun-zhao-liang-ge-zhe/


本文链接: http://www.dtmao.cc/news_show_100104.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?