博客
关于我
1539. Kth Missing Positive Number
阅读量:279 次
发布时间:2019-03-01

本文共 969 字,大约阅读时间需要 3 分钟。

为了解决这个问题,我们需要找到缺失在给定数组中的第k个正整数。数组中的数是严格递增的正整数,但可能存在缺失的数,我们需要找到这些缺失数中的第k个。

方法思路

我们可以使用两个变量来跟踪当前位置和缺失的数量。具体步骤如下:

  • 初始化两个变量count和cur,分别用于记录缺失的数量和当前位置。
  • 遍历数组中的每个元素,逐步检查是否存在缺失的数。
  • 当发现缺失的数时,继续检查直到找到第k个缺失的数。
  • 处理完数组后,继续检查后续可能的缺失数,直到找到第k个。
  • 这种方法确保了我们能够高效地找到第k个缺失的数,避免了不必要的重复计算。

    解决代码

    #include 
    using namespace std;int findKthPositive(vector
    & arr, int k) { int count = 0; int cur = 0; for (int num : arr) { cur++; while (cur < num) { count++; if (count == k) { return cur; } cur++; } } while (count < k) { cur++; count++; if (count == k) { return cur; } } return -1; // This line is theoretically unreachable as per problem constraints}

    代码解释

  • 初始化变量:count用于记录缺失的数量,cur用于跟踪当前位置。
  • 遍历数组:对于数组中的每个元素,先增加cur,然后检查是否存在缺失的数。如果发现缺失的数,继续检查直到找到第k个缺失的数。
  • 处理后续缺失数:处理完数组后,继续检查后续可能的缺失数,直到找到第k个。
  • 这种方法确保了我们能够高效地找到第k个缺失的数,避免了不必要的重复计算。

    转载地址:http://saqo.baihongyu.com/

    你可能感兴趣的文章
    python初步学习-python数据类型-集合(set)
    查看>>
    python列表生成字典_Python中将字典转换为列表的方法
    查看>>
    python列表对应元素合并为列表及判断一个列表是几维
    查看>>
    python+flask计算机毕业设计高校校园线上跳蚤市场的系统设计(程序+开题+论文)
    查看>>
    python+flask计算机毕业设计高校疫情防控管理平台(程序+开题+论文)
    查看>>
    Python+Jenkins+Allure Report接口自动化测试持续集成
    查看>>
    python+locust电商全流程性能测试
    查看>>
    Python函数运行的可执行文件的终端输出如何以一般方式静音?
    查看>>
    Python+Pytest+Allure+Git+Jenkins接口自动化框架
    查看>>
    python+pytest接口自动化 —— 参数关联
    查看>>
    python+pytest接口自动化 —— 参数关联
    查看>>
    python+pytest接口自动化 —— 自动化用例编写思路 (使用pytest编写一个测试脚本)
    查看>>
    Python+pytest接口自动化之cookie绕过登录(保持登录状态)
    查看>>
    python+pytest接口自动化:接口测试
    查看>>
    Python+requests+unittest执行接口自动化测试详情
    查看>>
    Python+requests+unittest执行接口自动化测试详情
    查看>>
    python+requests+unittest执行自动化接口测试!
    查看>>
    Python+Requests编码识别Bug
    查看>>
    Python+selenium —— UI自动化之鼠标操作
    查看>>
    Python+Selenium+Threading进行兼容性测试
    查看>>