İçeriğe geç

Listede eksik k. sayı

Kolay#binary-search#counting~20 dk

Görev tanımı

Problem

Bilet numaraları 1'den yukarı doğru dağıtılıyor ve nums kullanılanları, kesin artan ve hepsi pozitif olarak listeliyor. nums'ta görünmeyen k. en küçük pozitif sayıyı döndür; k en az 1. Sayıları tek tek dolaşmaktan daha hızlı bir çözüm hedefle.

Örnekler

Input:  nums = [2, 3, 4, 7, 11], k = 5
Output: 9
Neden: eksik sayılar 1, 5, 6, 8, 9, 10, ...
Input:  nums = [1, 2, 3, 4], k = 2
Output: 6
Neden: listenin içinde hiçbir şey eksik değil, cevap sonunun ötesinde
Input:  nums = [], k = 4
Output: 4
Neden: edge case: hiçbir şey kullanılmadıysa k. eksik sayı k'nın kendisidir

İpuçları

0 / 3

Hedef zaman
O(log n)
Hedef alan
O(1)

Kısıtlar

  • nums is strictly increasing
  • every value in nums is positive
  • k ≥ 1

Kodda değil de fikirde mi takıldın? İkili arama bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case