LeetCode 35: Ekleme Pozisyonunu Bulma – Google ve LLM Olmadan!
Merhaba! Bu yazıda, LeetCode’un 35. sorusu olan “Search Insert Position” (Ekleme Pozisyonunu Bulma) problemine Google veya herhangi bir büyük dil modeli kullanmadan nasıl yaklaşabileceğimizi inceleyeceğiz. Bu problem, bir dizi içinde belirli bir sayının eklenmesi gerektiği durumda, sayının doğru pozisyonunu bulmayı gerektirir. Öncelikle problemi daha iyi anlamak için sorunun tanımına bakalım. Sizi sıkmayacak şekilde adım adım ilerleyeceğiz.
Problem Tanımı: Sıralaılmış bir tamsayı dizisi nums ve bir hedef tamsayı target verildiğinde, target dizide mevcutsa indeksini, mevcut değilse target’ın eklenmesi gereken doğru indeksini bulun. Diğer bir deyişle, target’ı nums dizisine ekleyecek olursak, target hangi indekste olmalıdır?
Örnekler:
nums = [1,3,5,6], target = 5çıktı:2(5 zaten dizide ve indeksi 2)nums = [1,3,5,6], target = 2çıktı:1(2, 1 ve 3 arasına eklenmelidir)nums = [1,3,5,6], target = 7çıktı:4(7, dizinin sonuna eklenmelidir)
Çözüm: Bu problemi çözmek için en etkili yöntem ikili arama algoritmasıdır (Binary Search). İkili arama, sıralı bir dizide bir elemanı verimli bir şekilde aramak için kullanılan bir algoritmadır. Öncelikle, dizinin ortasındaki elemanı kontrol ederiz. Eğer hedef değer ortadaki elemandan küçükse, aramayı dizinin sol yarısında, büyükse sağ yarısında devam ettiririz. Bu işlemi, hedef değeri bulana veya arama alanı kalmayana kadar tekrarlarız. Hedef değer bulunmazsa, son arama yapılan indeks, hedef değerinin eklenmesi gereken indeks olur.
// Python kodu
def searchInsert(nums, target):
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return low
Bu kod, ikili arama kullanarak problemi etkili bir şekilde çözer. Kodun anlaşılır olması için yorum satırları ekledim. Ancak, bu sadece bir çözüm yolu. Başka alternatif çözümler de mevcuttur. Örneğin, doğrusal arama (Linear Search) kullanılabilir, ancak ikili arama daha verimlidir. Bu da zaman karmaşıklığını iyileştirir. Zaman karmaşıklığı O(log n) iken doğrusal arama O(n) zaman karmaşıklığına sahiptir. Bu fark özellikle büyük dizilerde önemli hale gelir. Ayrıca, kodunuzu iyileştirmek için daha fazla optimizasyon yapabilirsiniz.
Umarım bu açıklama size yardımcı olmuştur. Daha fazla LeetCode çözümü ve yazılım geliştirme ipuçları için fatihsoysal.com sitesini ziyaret edebilirsiniz. Başka bir problem çözümünde görüşmek üzere!
Faydalı Kaynaklar: