首页 > 其他分享 >Leetcode 4. 寻找两个正序数组的中位数(二分)

Leetcode 4. 寻找两个正序数组的中位数(二分)

时间:2023-03-20 16:48:08浏览次数:48  
标签:二分 正序 中位数 nums1 数组 n1 n2 Leetcode nums2

题目链接在这里:

是一道很好的二分题,一开始没有想到越界怎么处理,忽略了(m+n)/2一定介于min(n,m)和max(n,m)之间,因此如果确定在短的数组上进行二分就不用考虑越界问题了,其次没有考虑到当划分之后,左边区间的每一个点都小于右边区间的点,这是一个很重要的性质,但是最开始在当前策略有效性的判断上并没有考虑到这个,而是单独的对每一个数组的边界分别进行判断。

 1 class Solution(object):
 2     def findMedianSortedArrays(self, nums1, nums2) -> float:
 3         n1 = len(nums1)
 4         n2 = len(nums2)
 5         m = (n1 + n2+1) // 2
 6         if n1 > n2:
 7             return Solution.findMedianSortedArrays(self, nums2, nums1)
 8         low, high = 0, n1
 9         while low <= high:
10             mid = (low + high) // 2
11             midd = m - mid
12 
13             # print("low:",low,"high:",high,"mid:",mid)
14             lw1 = -1e7 if mid == 0 else nums1[mid-1]
15             lw2 = -1e7 if midd == 0 else nums2[midd-1]
16             hgh = 1e7 if mid == n1 else nums1[mid]
17             hgh2 = 1e7 if midd == n2 else nums2[midd]
18 
19             if lw1<=hgh2:
20                 low = mid+1
21                 an1,an2 = max(lw1,lw2),min(hgh,hgh2)
22                 # print (lw1, lw2)
23             else:
24                 high = mid - 1
25         if ((n1+n2)%2==1):
26             return an1
27         else:
28             return (an1+an2)/2.0
29 
30 
31 if __name__ == "__main__":
32     nums1 = [1, 2]
33     nums2 = [3, 4]
34     ans = Solution.findMedianSortedArrays(self=0, nums1=nums1, nums2=nums2)
35     print(ans)

 

标签:二分,正序,中位数,nums1,数组,n1,n2,Leetcode,nums2
From: https://www.cnblogs.com/keximeiruguo/p/17236817.html

相关文章

  • leetcode刷题--TypeError:object of type 'NoneType' has no len()/AttributeError: 'N
    错误:一.TypeError:objectoftype'NoneType'hasnolen()list=[]i=0j=0whilelen(list)<=len(nums1)+len(nums2):报错:TypeError:objectoftype'NoneType'ha......
  • LeetCode 3.无重复字符的最长子串
    题目链接在这里:​​3.无重复字符的最长子串-力扣(LeetCode)​​这道题学习了几何函数set()的用法1classSolution(object):2deflengthOfLongestSubstring(self,s:......
  • LeetCode 2.两数相加
    题目链接在这里:​​2.两数相加-力扣(LeetCode)​​这道题学了一些python类和子函数的语法,发现语法与C++有异曲同工之妙1classListNode:2def__init__(self,val=0,......
  • Leetcode 1.两数之和(hash)
    题目链接在这里:​​1.两数之和-力扣(LeetCode)​​这道题主要学习了python中哈希表的使用,类似于c++中的map容器1#暴力2#classSolution:3#deftwoSum(self,nu......
  • 【LeetCode贪心#10】划分字母区间(有涉及hash数组的使用)
    划分字母区间力扣题目链接(opensnewwindow)字符串S由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串......
  • #yyds干货盘点# LeetCode面试题:最大子数组和
    1.简述:给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。 示例1:输入:nums=[-2,1,-3,4,-......
  • #yyds干货盘点# LeetCode程序员面试金典:BiNode
    题目:二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求依然符合二叉搜索树的性质,转换操作应是原......
  • LeetCode435 -- 预定会议问题
    0.ref参考自1.题目描述预定会议问题:给定我们一堆区间,区间不能重叠(\([1,2]\)和\([2,3]\)的\(2\)不算重叠),求最多能保留多少个区间?做法:贪心,按【右端点】排序。......
  • LeetCode354 -- 最长上升子序列
    1.题目描述354.俄罗斯套娃信封问题2.思路非常明显的上升子序列问题。但是我在做的时候遇到了一个之前做\(LCS\)从来没考虑过的点。之前都是直接排序,而无论是......
  • LeetCode337周赛T4 -- 同余
    1.题目描述T42.思路其实本题非常简单。我们只需要知道一个概念:“同余”。即:\(a==b(modc)\),我们称\(a\)和\(b\)相等在\(modc\)意义下。知道了这个点,......