leetcode分类刷题:二分查找(Binary Search)(四、基于值域的数组/矩阵类型)

这篇具有很好参考价值的文章主要介绍了leetcode分类刷题:二分查找(Binary Search)(四、基于值域的数组/矩阵类型)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基于值域的二分法与基于定义域的题型不同,它的目标是从一“特殊排序序列”中确定“第k个元素值”,而不像基于定义域的题型是从排序序列中找小于等于特定target值的第一个索引;同时,针对“特殊排序序列”,往往需要嵌套使用双指针法进行操作,进一步增加了对应题型的难度。

378. 有序矩阵中第 K 小的元素

from typing import List
'''
378. 有序矩阵中第 K 小的元素
题目描述:给你一个n x n矩阵matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于O(n2) 的解决方案。
示例 1:
    输入:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
    输出:13
    解释:矩阵中的元素为 [1,5,9,10,11,12,13,13,15],第 8 小元素是 13
题眼:每行和每列元素均按升序排序 有序矩阵
思路:(有点难度,看了官方解答才明白)值域的二分法:确定左右两侧边界为matrix[0][0]=leftVal和matrix[n-1][n-1]=rightVal,二分后统计小于等于midVal的数量,
      讨论与k的大小关系,保证第k小的数始终位于leftVal~rightVal之间(即保证在左闭右闭区间内[leftVal,rightVal]),当leftVal==rightVal时,第k小的数即被找出
      这道题就是在“二分式”缩小目标值的值域区间范围!也可以看到,这个题的target值不像之前一样是给定然后确定存在位置了,是要确定其值。
'''


class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        leftVal, rightVal = matrix[0][0], matrix[n-1][n-1]
        # 确定target所在的区间[leftVal, rightVal],对矩阵中小于等于中间值midVal的元素数目进行统计
        # 关键思路:如果数目小于k,说明target>midVal;即左边界leftVal = midVal + 1
        # 如果数目等于k,说明target<=midVal;即右边界rightVal = midVal
        # 如果数目大于k,说明target<=midVal;即右边界rightVal = midVal
        while leftVal < rightVal:
            midVal = leftVal + (rightVal-leftVal) // 2
            count = self.checkSmallEqualMid(matrix, midVal)  # 表示小于等于mid的数量
            if count < k:  # 第k小的数在midVal的右侧,且不包含midVal
                leftVal = midVal + 1
            elif count >= k:  # 第k小的数在midVal的左侧,可能包含midVal
                rightVal = midVal
        return leftVal

    def checkSmallEqualMid(self, matrix: List[List[int]], midVal: int) -> int:
        n = len(matrix)
        # 双指针:根据矩阵的特殊性质,从左下角开始统计
        i, j = n - 1, 0
        count = 0
        while i >= 0 and j <= n - 1:  # 索引必须在边界之内
            if matrix[i][j] <= midVal:
                count += i + 1  # 对应行及行以上全部统计
                j += 1  # 并更新列数
            else:
                i -= 1  # 更新行数
        return count


if __name__ == '__main__':
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            matrix = []
            for row in in_line[1].strip()[1: -4].split(']')[:-1]:
                matrix.append([int(n) for n in row.split('[')[1].split(',')])
            k = int(in_line[2])
            # print(matrix, k)
            print(obj.kthSmallest(matrix, k))
        except EOFError:
            break

373. 查找和最小的 K 对数字

from typing import List
'''
373. 查找和最小的 K 对数字
题目描述:给定两个以 升序排列 的整数数组 nums1 和 nums2,以及一个整数 k。
定义一对值(u,v),其中第一个元素来自nums1,第二个元素来自 nums2。
请找到和最小的 k个数对(u1,v1), (u2,v2) ... (uk,vk)。
示例 1:
    输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
    输出: [1,2],[1,4],[1,6]
    解释: 返回序列中的前 3 对数:
        [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
题眼:组合num1为行索引,num2为列索引,可实现 每行和每列元素均按升序排序 有序矩阵,类似于”378. 有序矩阵中第 K 小的元素“
思路:值域二分法,注意返回的不是第k小,而是前k小(看了官网解析也觉得很难,这个题应该更适合其它算法来解)
'''


class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        result = []
        m, n = len(nums1), len(nums2)
        # 第一步,值域二分法找到第k小的数,确定pairSum所在的区间[leftVal, rightVal],对矩阵中小于等于中间值midVal的元素数目进行统计
        leftVal, rightVal = nums1[0]+nums2[0], nums1[m-1]+nums2[n-1]
        while leftVal < rightVal:
            midVal = (leftVal + rightVal) // 2
            count = self.checkSmallEqualMid(nums1, nums2, midVal)  # 表示小于等于中间值midVal的数量
            if count < k:  # 第k小的数在midVal的右侧,且不包含midVal
                leftVal = midVal + 1
            elif count >= k:  # 第k小的数在midVal的左侧,可能包含midVal
                rightVal = midVal
        pairSum = leftVal

        # 第二步,将小于pairSum的数对升序添加到result中
        # 分为两步添加是为了避免等于pairSum的数对和太多,导致所有小于的没有被添加到result中
        # 双指针:根据两个数组的特殊性质,i取nums1的最小值位置,j取nums2的最大值位置(以nums1为基准进行)
        i, j = 0, len(nums2) - 1
        while i < len(nums1) and j >= 0:  # 索引必须在边界之内
            if nums1[i] + nums2[j] < pairSum:
                for t in range(j + 1):
                    result.append([nums1[i], nums2[t]])
                    # if len(result) == k:  # 这里可以不用判断,小于pairSum的数对一定小于k个
                    #     return result
                i += 1
            elif nums1[i] + nums2[j] >= pairSum:
                j -= 1
        # 以下过程是上述双指针法 的等价形式
        # i2 = n - 1
        # for i1 in range(m):
        #     while i2 >= 0 and nums1[i1] + nums2[i2] >= pairSum:  # 用while直到小于pairSum的数对出现
        #         i2 -= 1
        #     for j in range(i2 + 1):  # 将该索引之前的nums2构成的数对,包括本身,全部添加到result
        #         result.append([nums1[i1], nums2[j]])
        #         if len(result) == k:
        #             return result

        # 第三步,将等于pairSum的数对升序添加到result中
        # 双指针:根据两个数组的特殊性质,i取nums1的最小值位置,j取nums2的最大值位置(以nums1为基准进行)
        i, j = 0, len(nums2) - 1
        while i < len(nums1) and j >= 0:  # 索引必须在边界之内
            if nums1[i] + nums2[j] < pairSum:
                i += 1
            elif nums1[i] + nums2[j] > pairSum:
                j -= 1
            else:
                t = j  # 添加nums2元素时考虑重复情况,同时j的位置要被记录而不能被更新
                while t >= 0 and nums1[i] + nums2[t] == pairSum:
                    result.append([nums1[i], nums2[t]])
                    if len(result) == k:
                        return result
                    t -= 1
                i += 1
        # 以下过程是上述双指针法 的等价形式
        # i2 = n - 1
        # for i1 in range(m):
        #     while i2 >= 0 and nums1[i1] + nums2[i2] > pairSum:  # 用while过滤掉大于pairSum的数对
        #         i2 -= 1
        #     j = i2
        #     while j >= 0 and nums1[j] + nums2[i2] == pairSum:  # 用while是为了将nums2中的全部重复元素添加上
        #         result.append([nums1[i1], nums2[j]])
        #         if len(result) == k:
        #             return result
        #         j -= 1
        return result

    def checkSmallEqualMid(self, nums1: List[int], nums2: List[int], midVal: int) -> int:
        # 双指针:根据两个数组的特殊性质,i取nums1的最小值位置,j取nums2的最大值位置
        i, j = 0, len(nums2) - 1
        count = 0
        while i < len(nums1) and j >= 0:  # 索引必须在边界之内
            if nums1[i] + nums2[j] <= midVal:
                count += j + 1  # 对应nums2位置元素及之前的全部统计
                i += 1
            else:
                j -= 1
        return count


if __name__ == '__main__':
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            nums1 = [int(n) for n in in_line[1].strip().split('[')[1].split(']')[0].split(',')]
            nums2 = [int(n) for n in in_line[2].strip().split('[')[1].split(']')[0].split(',')]
            k = int(in_line[3])
            # print(nums1, nums2, k)
            print(obj.kSmallestPairs(nums1, nums2, k))
        except EOFError:
            break

719. 找出第 K 小的数对距离

from typing import List
'''
719. 找出第 K 小的数对距离
题目描述:数对 (a,b) 由整数 a 和 b 组成,其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ,数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。
返回 所有数对距离中 第 k 小的数对距离。
示例 1:
    输入:nums = [1,3,1], k = 1
    输出:0
    解释:数对和对应的距离如下:
    (1,3) -> 2
    (1,1) -> 0
    (3,1) -> 2
    距离第 1 小的数对是 (1,1) ,距离为 0 。
题眼:第k小,必然是要经过排序的
思路:排序+值域二分法(完全想不到和“378. 有序矩阵中第 K 小的元素”、“373. 查找和最小的 K 对数字”是类似题型:
注意最小取值为0,最大为末端减去首端)+双指针
'''


class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        # 第一步,将数组升序排列
        nums.sort()
        n = len(nums) - 1
        # 第二步,值域二分法:确保第k小的 数对距离,确定所在的区间[leftVal, rightVal]
        leftVal, rightVal = 0, nums[n] - nums[0]  # 注意最小取值为0,最大为末端减去首端
        while leftVal < rightVal:
            midVal = (leftVal + rightVal) // 2
            count = self.countSmallEqual(nums, midVal)  # 表示小于等于中间值midVal的数量
            if count < k:  # 第k个数对距离 一定大于midVal
                leftVal = midVal + 1
            elif count >= k:  # 第k个数对距离 可能小于或等于midVal
                rightVal = midVal
        return leftVal

    def countSmallEqual(self, nums: List[int], midVal: int) -> int:
        # 双指针统计小于等于midVal的数对距离个数
        count = 0
        i, j = 0, 1  # i,j指向数组第一、第二位置
        while i < len(nums) - 1:  # i<j所以i不能取到最后一个索引
            if j < len(nums) and nums[j] - nums[i] <= midVal:
                j += 1
            elif j < len(nums) and nums[j] - nums[i] > midVal:  # 满足统计条件:索引全部有效时,第一次出现超过midVal的距离时,
                # 把前面满足小于等于midVal的距离对全部添加上
                count += (j - i - 1)
                i += 1
            elif j == len(nums):  # 当j已经遍历到头时,与上面满足统计条件的操作一致,可以合并
                count += (j - i - 1)
                i += 1
        return count


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]
            k = int(in_line[2])
            print(obj.smallestDistancePair(nums, k))
        except EOFError:
            break

个人总结体会

通过刷上述几道题目,除了掌握了基于值域的二分法步骤和模板,也同时掌握了对于行列递增的矩阵、两个递增的数组求和、单个递增的数组求元素对距离 这种“特殊序列”里用双指针法确定小于等于某一数值的元素或组合个数。文章来源地址https://www.toymoban.com/news/detail-674472.html

到了这里,关于leetcode分类刷题:二分查找(Binary Search)(四、基于值域的数组/矩阵类型)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题704、35、34数组二分查找) 2023.4.17

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 数组是由n(n=1)个 相同类型 的数据元素

    2024年02月05日
    浏览(49)
  • 【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   mySqrt ( self ,  x :   int )   -   int :       

    2024年02月04日
    浏览(65)
  • LeedCode刷题---二分查找类问题

    顾得泉: 个人主页 个人专栏: 《Linux操作系统》  《C/C++》  《LeedCode刷题》 键盘敲烂,年薪百万! 题目链接: 二分查找        给定一个  n  个元素有序的(升序)整型数组  nums  和一个目标值  target   ,写一个函数搜索  nums  中的  target ,如果目标值存在返回

    2024年02月04日
    浏览(43)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • Leetcode 1011. Capacity To Ship Packages Within D Days (Binary Search经典)

    Capacity To Ship Packages Within D Days Medium 8.6K 179 Companies A conveyor belt has packages that must be shipped from one port to another within days days. The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maxi

    2024年02月09日
    浏览(33)
  • 【算法刷题】—7.12二分查找应用,数组处理

    🧛‍♂️ 个人主页: 杯咖啡 💡进步是今天的活动,明天的保证! ✨目前正在学习:SSM框架,算法刷题 🙌 牛客网 ,刷算法过面试的神级网站, 用牛客你也牛。 👉免费注册和我一起学习刷题👈 🐳希望大家多多支持🥰一起进步呀! 😎Love is the one thing we’are capable of perc

    2023年04月08日
    浏览(68)
  • 算法刷题Day1 二分查找+移除元素

    代码随想录-数组-1.数组理论基础 数组是存放在 连续内存空间 上的 相同类型 数据的 集合 优点:常数时间复杂度访问元素 缺点: 在删除或者增添元素的时候,就难免要移动其他元素的地址 ,时间复杂度为O(n) 代码随想录-数组-2.二分查找 前提条件 二分查找前提条件: 数组

    2024年02月10日
    浏览(54)
  • leetcode 二分查找小结

    原始思路: 但是,挪一挪的步骤最差的时候时间复杂度也能达到O(n),所以另一种避免这种情况的思路是我们分别使用二分查找去寻找区间的最左和最右。 上面的寻找target的代码(while …)无法精确地找到最左,因此我们需要对其进行一些改写。关键是要在找到一个值的时候不

    2024年02月08日
    浏览(55)
  • # - LeetCode 704-二分查找 |LeetCode 27-移除元素

    ##  LeetCode 704-二分查找 -题目描述:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target , -写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  , 写一个函数搜索 nums

    2024年02月16日
    浏览(53)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包