首页 > 编程语言 >LeetCode-Python-1539. 第 k 个缺失的正整数(二分)

LeetCode-Python-1539. 第 k 个缺失的正整数(二分)

时间:2024-08-29 12:24:09浏览次数:12  
标签:arr right 正整数 Python 复杂度 缺失 LeetCode 1539 left

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 1:

输入:arr = [2,3,4,7,11], k = 5
输出:9
解释:缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

示例 2:

输入:arr = [1,2,3,4], k = 2
输出:6
解释:缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

提示:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • 对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

进阶:

你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗?

第一种思路:

线性遍历每一个数字看它在不在 arr 里,比较麻瓜没有实现。

时间复杂度:O(K + N)

空间复杂度:O(N)

第二种思路:

比较有趣,利用到了二分的方法。

对于一个 arr[i] 来说,它左边的缺失正整数的数量 n 应该是 = arr[i] - (i + 1)。

我们通过判断 n 和 k 的关系,就可以不断缩减一半的区间。

当二分循环结束的时候,我们应该有 left = right + 1,此时要输出的答案 res 满足 arr[right] < res < arr[left],

假设 arr[right] 之前没有正整数缺失,我们直接返回 arr[right] + k 即可,

但是现在如果考虑它之前有缺失的情况,我们需要返回的就是 arr[right] + (k -  (arr[right] - (right + 1))) = k + (right + 1) = k + left。

这个返回值的计算非常巧妙。

时间复杂度:O(logn)

空间复杂度:O(1)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # the num of missing positive num before arr[i] = 
        # arr[i] - (i + 1)
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            n = arr[mid] - (mid + 1)
            if n < k:
                left = mid + 1
            else:
                right = mid - 1
        # right = left + 1
        # arr[right] < res < arr[left]
        # before arr[right], we have missing positive num = arr[right] - (right + 1)
        # if that is 0, then we return arr[right] + k
        # if that part is not 0, we have to eliminate that from k
        # return arr[right] + (k - arr[right] - (right + 1))
        return left + k

标签:arr,right,正整数,Python,复杂度,缺失,LeetCode,1539,left
From: https://blog.csdn.net/qq_32424059/article/details/141654928

相关文章

  • 探索 AI Agents:从理念到 Python 实际运用
    作者:老余捞鱼原创不易,转载请标明出处及原作者。写在前面的话:    本文主要介绍了如何利用人工智能代理(AIAgents)从概念到Python中的实际应用,以及如何构建一个内容创作工作流程,通过多个代理协作完成从视频分析到博客撰写的复杂任务,完成后也许这会改变你对人工智能......
  • 期权定价模型(如Black-Scholes模型)和利率模型中的单因子模型的Python实现案例
    一:期权定价模型(如Black-Scholes模型)的实现期权定价模型(如Black-Scholes模型)是用来确定期权合理价格的数学模型。这些模型基于一定的假设,考虑了多种因素,如标的资产价格、期权的行权价格、期权的到期时间、无风险利率以及标的资产的波动性等。接下来将使用Python来实现这个模......
  • Python 项目及依赖管理工具技术选型
    Python项目及依赖管理工具,类似于Java中的Maven与Node中的npm+webpack,在开发和维护项目时起着重要的作用。使用适当的依赖管理工具可以显著提高开发效率,减少依赖冲突,确保项目的稳定性、可靠性和安全性。一、常见项目及依赖管理工具需具备的功能1.依赖管理(1)自动化依赖......
  • python 包引入顺序
    isorthttps://pycqa.github.io/isort/isort·PyPIhttps://pypi.org/project/isort/Beforeisort:frommy_libimportObjectimportosfrommy_libimportObject3frommy_libimportObject2importsysfromthird_partyimportlib15,lib1,lib2,lib3,lib......
  • 【基于python tkinter的本地小说阅读器的界面改善】
    系列文章链接1.记录基于Pythontkinter的音乐播放器的实现过程2.基于pythontkinter的本地小说阅读器基于pythontkinter的本地小说阅读器的界面改善系列文章链接前言一、界面改进的地方二、界面展示三、代码前言上次写了一篇《基于pythontkinter的本地小说阅......
  • 基于 Selenium 的 Python 自动化测试框架
    SeleniumBase:功能全面的浏览器自动化框架。该项目是基于Selenium的Python自动化测试框架,集成了爬虫、自动化测试和生成报告等多种功能。它提供了丰富的示例,并且独特的UC模式,可以帮助开发者在进行浏览器自动化操作时避免被检测出来。from seleniumbase import BaseCaseBa......
  • 一起学习LeetCode热题100道(61/100)
    61.分割回文串(学习)给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。返回s所有可能的分割方案。示例1:输入:s=“aab”输出:[[“a”,“a”,“b”],[“aa”,“b”]]示例2:输入:s=“a”输出:[[“a”]]提示:1<=s.length<=16s仅由小写英文字母......
  • Python——集合基本操作以及哈希函数
    Python中的集合(Set)是一个无序的、不包含重复元素的数据结构。集合主要用于数学上的集合操作,如并集、交集、差集和对称差集等。集合使用大括号 {} 来表示,但注意空集合不能使用 {} 表示(这会创建一个空字典),而应该使用 set() 来创建。创建集合1.使用大括号 {}:这是最直接......
  • Python——异常
    内置异常合集Python提供了许多内置的异常类,用于处理不同类型的错误情况。这些异常类大多数都继承自 BaseException,而 Exception 是所有内建的非系统退出类异常的超类。以下是一些常见的Python内置异常及其简要说明:继承自 Exception 的异常ArithmeticError:所有数值计......
  • 用python写一个生产管理算法
    在生产管理中,算法可以帮助优化生产流程、提高效率和降低成本。一个简单的生产管理算法可能包括任务分配、资源调度、生产线平衡等方面。下面我将提供一个基本的任务分配算法的示例,这个算法将基于工人的技能和可用性来分配任务。```pythonclassWorker:def__init__(self,id......