Listede eksik k. sayı
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
Hiçbir şey eksik olmasaydı i indeksindeki değer i + 1 olurdu. Gerçek değer ile i + 1 arasındaki fark sana işe yarar bir şey söyler.
nums[i] eksi (i + 1), nums[i]'nin altındaki eksik değerlerin sayısıdır ve i büyüdükçe hiç azalmaz; bu yüzden ikili aramayla aranabilir.
Bu sayının k'ya ulaştığı ilk indeksi bul. O indeks lo ise cevabın altında tam olarak lo liste değeri vardır, yani cevap lo + k.
- Hedef zaman
- O(log n)
- Hedef alan
- O(1)
Kısıtlar
- nums is strictly increasing
- every value in nums is positive
- k ≥ 1
Çözüm
i indeksinde liste i + 1 sayı kullanmıştır; yani nums[i]'nin altında nums[i] eksi (i + 1) sayı eksiktir ve bu sayı liste boyunca hiç azalmaz. İkili arama (binary search) en az k sayının eksik olduğu ilk indeks olan lo'yu, yoksa listenin uzunluğunu bulur. Cevap o zaman tam olarak lo kullanılmış sayıdan sonra durur ve aralarında olmayan k. sayıdır, yani lo + k. Zaman O(log n), alan O(1).
def kth_missing(nums, k):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] - (mid + 1) < k: # fewer than k missing below nums[mid]
lo = mid + 1
else:
hi = mid
return lo + k # lo used numbers lie below the answer
print(kth_missing([2, 3, 4, 7, 11], 5)) # -> 9
print(kth_missing([1, 2, 3, 4], 2)) # -> 6
print(kth_missing([], 4)) # -> 4
print(kth_missing([5, 6, 7], 3)) # -> 3Kodda değil de fikirde mi takıldın? İkili arama bunu anlatıyor.