0004. Median of Two Sorted Arrays | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0004.Median-of-Two-Sorted-Arrays/

[hujun2020]

看懂了算我输

[halfrost]

@hujun2020 😭我描述的这么烂么。

[chenqi146]

我感觉挺好懂的呀

[hujun2020]

@chenqi146 我感觉挺好懂的呀

嗯 老简单了 我看你过几天还能不能自己写出来

[franktrue]

这个题题目描述的不清楚，并没有提到说合并数组，要不是有example的话，很容易理解错误。当然也有可能是我题刷的太少，没有意会到~

[halfrost]

@franktrue 是的，题目中没有说的特别清楚。

[chiyoi]

py checkin

        if not len(nums1):
            return nums2[len(nums2) // 2] if len(nums2) % 2 else (nums2[len(nums2) // 2 - 1] + nums2[len(nums2) // 2]) / 2
        if not len(nums2):
            return nums1[len(nums1) // 2] if len(nums1) % 2 else (nums1[len(nums1) // 2 - 1] + nums1[len(nums1) // 2]) / 2
        if len(nums1) > len(nums2):
            t = nums2
            nums2 = nums1
            nums1 = t
            del t
######################################################
        left = (len(nums1) + len(nums2)) // 2
        leftIn1 = 0 #以中位数左侧的元素个数作标记，leftIn1表示有这么多在nums1列表
                           #left表示总共有这么多在中位数左边，left - leftIn1就是nums2中的个数
        cutPoint1 = 0
        cutPoint2 = len(nums1)
        while True:
            if not leftIn1:
                if nums1[leftIn1] < nums2[left - leftIn1 - 1]:
                    if cutPoint2 < cutPoint1:
                        cutPoint2 = cutPoint1
                    #move right
                else:
                    break
            elif not left - leftIn1:
                if nums1[leftIn1 - 1] > nums2[left - leftIn1]:
                    if cutPoint2 > cutPoint1:
                        cutPoint2 = cutPoint1
                    #move left
                else:
                    break
            else:
                if nums1[leftIn1] < nums2[left - leftIn1 - 1]:
                    if cutPoint2 < cutPoint1:
                        cutPoint2 = cutPoint1
                    #move right
                elif nums1[leftIn1 - 1] > nums2[left - leftIn1]:
                    if cutPoint2 > cutPoint1:
                        cutPoint2 = cutPoint1
                    #move left
                else:
                    break
            cutPoint1 = leftIn1
            leftIn1 = (cutPoint1 + cutPoint2) // 2
            if leftIn1 == cutPoint1:
                if cutPoint2 < cutPoint1 and leftIn1:
                    leftIn1 -= 1
                elif cutPoint2 > cutPoint1 and leftIn1 < len(nums1):
                    leftIn1 += 1
            if not leftIn1 or leftIn1 == len(nums1):
                break
####################################################
        if (len(nums1) + len(nums2)) % 2:
            if leftIn1 == len(nums1):
                return nums2[left - leftIn1]
            if left - leftIn1 == len(nums2):
                return nums1[leftIn1]
            return min(nums1[leftIn1], nums2[left - leftIn1])
        return (max(nums1[leftIn1 - 1] if leftIn1 else nums2[left - leftIn1 - 1], nums2[left - leftIn1 - 1] if left - leftIn1 else nums1[leftIn1 - 1]) + min(nums1[leftIn1] if leftIn1 < len(nums1) else nums2[left - leftIn1], nums2[left - leftIn1] if left - leftIn1 < len(nums2) else nums1[leftIn1])) / 2

为什么我的二分搜索这么长……

[chiyoi]

按s自动跳转搜索框这是什么神秘设定，都打不了单词了

[halfrost]

按s自动跳转搜索框这是什么神秘设定，都打不了单词了

@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？

[chiyoi]

按s自动跳转搜索框这是什么神秘设定，都打不了单词了

@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？

英文输入，就只按s，我是macOS11.5，safari

[halfrost]

按s自动跳转搜索框这是什么神秘设定，都打不了单词了

@CHIYOI 我刚刚试了一下，不会自动跳转搜索框呀。你是怎么操作的呢？就只按键盘上的字母键 s ？

英文输入，就只按s，我是macOS11.5，safari

@CHIYOI 我复现了。确实有问题。按 s 和 ？都会有这个问题。（别问我是怎么发现 ？ 也会触发，因为我把键盘上所有的键都按了一遍。😄）我周末查查是什么问题哈~ 感觉是 hugo 框架的问题。

[yshdzw]

Runtime: 8 ms, faster than 97.53% of Go online submissions for Median of Two Sorted Arrays. Memory Usage: 5.3 MB, less than 82.73% of Go online submissions for Median of Two Sorted Arrays.

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var (
        len1 int = len(nums1)
        len2 int = len(nums2)
    )

    if len1 == 0 && len2 == 0 {
        return 0
    }

    numsT := nums1
    if len1 == 0 {
        numsT = nums2
    }

    if len1 == 0 || len2 == 0 {
        len3 := len(numsT)
        div, mod := len3/2, len3%2
        if mod == 0 {
            return float64((numsT[div-1] + numsT[div])) / 2
        } else {
            return float64(numsT[div])
        }

    } else {
        // 思路：
        // 已知nums1和nums2均是有序的，可设计一种切换遍历的机制。
        // 通过div和mod来判断切换遍历提前结束，并计算中位数。
        //
        // 结束遍历的判断条件：
        //  遍历次数count 等于 div
        // 计算中位数：
        //  1、mod等于0时，中位数等于当前遍历的数；
        //  2、mod等于1时，中位数等于(前一个遍历的数+当期遍历的数)/2；
        //

        var (
            div   int = (len1 + len2) / 2
            mod   int = (len1 + len2) % 2
            n     int = 0 // nums1_index
            m     int = 0 // nums2_index
            count int = 0
            pre       = 0
            curr      = 0
        )

        for {
            // 条件1：nums1已经遍历完，但nums2还没有遍历完，numsT切片切换到nums2。
            // 条件2：nums2已经遍历完，但nums1还没有遍历完，numsT切片切换到nums1。
            // 条件3：nums1[n]大于等于nums2[n], numsT切片切换到nums2。
            // 条件4：nums1[n]小于nums2[n], numsT切片切换到nums1。
            if n >= len1 && m < len2 {
                numsT = nums2[m:]
                m++
            } else if m >= len2 && n < len1 {
                numsT = nums1[n:]
                n++
            } else if nums1[n] >= nums2[m] {
                numsT = nums2[m:]
                m++
            } else if nums1[n] < nums2[m] {
                numsT = nums1[n:]
                n++
            }

            curr = numsT[0] // 取出0号值
            count++         // 遍历了一次
            if (count - 1) == div {
                break
            }
            pre = curr
        }

        // 计算中位数
        if mod == 0 {
            return float64(pre+curr) / 2
        } else {
            return float64(curr)
        }
    }
}

[ls-2018]

@yshdzw Runtime: 8 ms, faster than 97.53% of Go online submissions for Median of Two Sorted Arrays. Memory Usage: 5.3 MB, less than 82.73% of Go online submissions for Median of Two Sorted Arrays.

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
  var (
      len1 int = len(nums1)
      len2 int = len(nums2)
  )

  if len1 == 0 && len2 == 0 {
      return 0
  }

  numsT := nums1
  if len1 == 0 {
      numsT = nums2
  }

  if len1 == 0 || len2 == 0 {
      len3 := len(numsT)
      div, mod := len3/2, len3%2
      if mod == 0 {
          return float64((numsT[div-1] + numsT[div])) / 2
      } else {
          return float64(numsT[div])
      }

  } else {
      // 思路：
      // 已知nums1和nums2均是有序的，可设计一种切换遍历的机制。
      // 通过div和mod来判断切换遍历提前结束，并计算中位数。
      //
      // 结束遍历的判断条件：
      //  遍历次数count 等于 div
      // 计算中位数：
      //  1、mod等于0时，中位数等于当前遍历的数；
      //  2、mod等于1时，中位数等于(前一个遍历的数+当期遍历的数)/2；
      //

      var (
          div   int = (len1 + len2) / 2
          mod   int = (len1 + len2) % 2
          n     int = 0 // nums1_index
          m     int = 0 // nums2_index
          count int = 0
          pre       = 0
          curr      = 0
      )

      for {
          // 条件1：nums1已经遍历完，但nums2还没有遍历完，numsT切片切换到nums2。
          // 条件2：nums2已经遍历完，但nums1还没有遍历完，numsT切片切换到nums1。
          // 条件3：nums1[n]大于等于nums2[n], numsT切片切换到nums2。
          // 条件4：nums1[n]小于nums2[n], numsT切片切换到nums1。
          if n >= len1 && m < len2 {
              numsT = nums2[m:]
              m++
          } else if m >= len2 && n < len1 {
              numsT = nums1[n:]
              n++
          } else if nums1[n] >= nums2[m] {
              numsT = nums2[m:]
              m++
          } else if nums1[n] < nums2[m] {
              numsT = nums1[n:]
              n++
          }

          curr = numsT[0] // 取出0号值
          count++         // 遍历了一次
          if (count - 1) == div {
              break
          }
          pre = curr
      }

      // 计算中位数
      if mod == 0 {
          return float64(pre+curr) / 2
      } else {
          return float64(curr)
      }
  }
}

你这时间复杂度是O(n)吧

[Andylixunan]

@CHIYOI 按s自动跳转搜索框这是什么神秘设定，都打不了单词了

https://github.com/alex-shpak/hugo-book/issues/134

[bearlly]

这个有点烂，建议用大小堆来实现

[whl5627445]

确实。。没太看懂。。

[whl5627445]

能提个建议吗， 代码可不可以贴全， 有的函数没有贴上去，想运行一下看看效果还要重写缺失的函数， 挺蛋疼的， 这个题好像没有max函数？

[whl5627445]

@halfrost

[halfrost]

能提个建议吗， 代码可不可以贴全， 有的函数没有贴上去，想运行一下看看效果还要重写缺失的函数， 挺蛋疼的， 这个题好像没有max函数？

@whl5627445 你这个建议很好。代码并不是我故意不贴全。是因为我把所有题的代码放在一个包里面了。一个包里面的函数只能唯一。如果每道题都要写 max 函数，那么就需要写 max_XXXX （带题号）变成不同的函数。我目前还没有这样做。

[contykang]

@whl5627445 能提个建议吗， 代码可不可以贴全， 有的函数没有贴上去，想运行一下看看效果还要重写缺失的函数， 挺蛋疼的， 这个题好像没有max函数？

函数很简单。可以自己写一下。

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

[fyydnz53]

这就是hard级别的思路吗？看得有点悬乎

[clarencedo]

用堆排去找中位数，时间复杂度是不是也满足O(log(m+n))

[clarencedo]

@bearlly 这个有点烂，建议用大小堆来实现

我也觉得用堆排来弄更好，但是适合动态数组。

[hanniballei]

if (len(nums1)+len(nums2))&1 == 1 { return float64(midLeft) } 请问一下这个代码是什么含义

[Xuzan9396]

先排序，然后奇数取中间，偶数取平均值