草庐IT

1539. 第 k 个缺失的正整数

spark打酱油 2023-09-16 原文

解题思路

1.知识点

  • 方法一：枚举
    思路与算法
    我们可以顺序枚举。
    枚举法
    由于数组是严格递增的，所以可以认为一个不缺失的数组是从1开始的：nums = [1,2,3,4,...].我们可以从头遍历arr数组，并以不缺失数组为基准进行对比，具体来说：
    初始化基准 pivot = 1，并令i = 1从头遍历数组arr。
    若当前arr[i] == pivot，说明当前i位置之前都不缺元素，继续向后遍历i++，
    否则说明缺失正整数pivot，用一个变量count记录已经找到的缺失个数，count++，直到找到第k个缺失的正整数。

  • 变量注解
    var count = 0 // 缺失个数
    var pivot = 1 // 当前应该出现的数
    var index = 0 // 数组指针

2.代码

object Solution {
    def findKthPositive(arr: Array[Int], k: Int): Int = {
    var count = 0
    var pivot = 1
    var index = 0
    while (count<k){
      if(arr(index)==pivot){
        if((index+1<arr.length)){
          index = index+1
        }else index = index
      } else count=count+1
      pivot=pivot+1
    }
    return pivot-1
  }
}

3.复杂度

  • 时间复杂度： O(n+k), n是数组长度，k是最坏情况下遍历完数组还没有缺失，则还需要再对count累加k次.
  • 空间复杂度： O(1)，仅使用常数空间
缺失1539pivotcount

有关1539. 第 k 个缺失的正整数的更多相关文章

  1. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  2. ruby-on-rails - 缺失区域；使用 :region option or export region name to ENV ['AWS_REGION' ] - 2

    我知道还有其他相同的问题，但他们没有解决我的问题。我不断收到错误:Aws::Errors::MissingRegionErrorinBooksController#create,缺少区域；使用:region选项或将区域名称导出到ENV['AWS_REGION']。但是，这是我的配置开发.rb:config.paperclip_defaults={storage::s3,s3_host_name:"s3-us-west-2.amazonaws.com",s3_credentials:{bucket:ENV['AWS_BUCKET'],access_key_id:ENV['AWS_ACCE

  3. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  4. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

  5. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  6. ruby - 如何在 Ruby 中生成一个非常大的随机整数？ - 2

    我想在ruby​​中生成一个64位整数。我知道在Java中你有很多渴望，但我不确定你会如何在Ruby中做到这一点。另外，64位数字中有多少个字符？这是我正在谈论的示例......123456789999。@num=Random.rand(9000)+Random.rand(9000)+Random.rand(9000)但我认为这是非常低效的，必须有一种更简单、更简洁的方法来做到这一点。谢谢! 最佳答案 rand可以将范围作为参数:pa=rand(2**32..2**64-1)#=>11093913376345012184putsa.

  7. ruby-on-rails - RoR中是否有任何内置方法可以为整数填充零？ - 2

    如果我想要“00001”而不是“1”，除了我自己写填零方法之外，有没有内置的方法可以帮助我为整数填零？ 最佳答案 puts"%05d"%1#00001参见:String::%,Kernel::sprintf这是正在发生的事情。%左侧的"%05d"是C风格的格式说明符。%右边的变量就是要格式化的东西。格式说明符可以像这样解码:%-格式说明符的开头0-用前导零填充5-长度为5个字符d-被格式化的是一个整数如果你要格式化多个东西，你会把它们放在一个数组中:"%d-%s"%[1,"One"]#=>1-one

  8. ruby-on-rails - 第 1 行中的引号缺失或遗漏 (CSV::MalformedCSVError) - 2

    我在ruby​​/rails中导入此CSV文件时遇到问题我得到的错误信息是这样的:Missingorstrayquoteinline1(CSV::MalformedCSVError)但我不确定发生了什么，因为我的CSV看起来非常好。以下是示例数据:"lesley_grades","lesley_id","last","first","active","site","cohort","section","sections_title","faculty","completed_term_cred","term","sec_start_date","sec_end_date","grade

  9. ruby - 使用 Ruby 将输入值适本地转换为整数或 float - 2

    我相信我对这个问题有一个很好的答案，但我想确保ruby​​-philes没有更好的方法来做到这一点。基本上，给定一个输入字符串，我想在适当的情况下将该字符串转换为整数，或在适当的情况下将其转换为float。否则，只返回字符串。我会在下面发布我的答案，但我想知道是否有更好的方法。例如:to_f_or_i_or_s("0523.49")#=>523.49to_f_or_i_or_s("0000029")#=>29to_f_or_i_or_s("kittens")#=>"kittens" 最佳答案 我会尽可能避免在Ruby中使用正则表达式

  10. ruby - 如何在 Ruby 中返回整数的固定长度二进制表示？ - 2

    我知道我可以使用Fixnum#to_s将整数表示为二进制格式的字符串。但是1.to_s(2)生成1而我希望它生成00000001。我怎样才能使所有返回的字符串都以零作为填充到8个字符？我可以使用类似的东西:binary="#{'0'*(8-(1.to_s(2)).size)}#{1.to_s(2)}"if(1.to_s(2)).size但这看起来不是很优雅。 最佳答案 使用字符串格式。"%08b"%1#=>"00000001" 关于ruby-如何在Ruby中返回整数的固定长度二进制表示？

随机推荐