kth-missing-positive-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array <code>arr</code> of positive integers sorted in a strictly increasing order, and an integer <code>k</code>.

Return the <code>kth</code> positive integer that is missing from this array.

&nbsp;
Example 1:

<pre>
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th&nbsp;missing positive integer is 9.
</pre>

Example 2:

<pre>
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>arr[i] &lt; arr[j]</code> for <code>1 &lt;= i &lt; j &lt;= arr.length</code></li>
</ul>

&nbsp;
Follow up:

Could you solve this problem in less than O(n) complexity?

findKthPositive

Kth Missing Positive Number

Append K Integers With Minimal Sum

append-k-integers-with-minimal-sum

向数组中追加 K 个整数

Array

Binary Search

给你一个 严格升序排列&nbsp;的正整数数组 <code>arr</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。

请你找到这个数组里第&nbsp;<code>k</code>&nbsp;个缺失的正整数。

&nbsp;

示例 1：

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

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li>对于所有&nbsp;<code>1 &lt;= i &lt; j &lt;= arr.length</code>&nbsp;的 <code>i</code>&nbsp;和 <code>j</code> 满足&nbsp;<code>arr[i] &lt; arr[j]</code>&nbsp;</li>
</ul>

&nbsp;

进阶：

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