Sıralı Dizi Birleştirme: Java ile LeetCode Çözümü
LeetCode’un sıkça sorulan sorularından biri olan “Sıralı Dizi Birleştirme” problemi, iki sıralı diziyi tek bir sıralı dizide birleştirmeyi hedefler. Bu problem, algoritma ve veri yapıları bilginizi test eden önemli bir sorudur. Öncelikle problemi daha iyi anlamak için örnek bir senaryoya bakalım. İki sıralı dizimiz olduğunu varsayalım: nums1 = [1,2,3,0,0,0] ve nums2 = [2,5,6]. Amacımız, nums1 dizisinin sonuna nums2 dizisini ekleyerek, sonucu nums1 = [1,2,2,3,5,6] olacak şekilde birleştirmektir. Bu problemi nasıl çözebileceğimize bakalım.
Problem Çözümüne Yöntemler
Bu problemi çözmek için birkaç yöntem kullanabiliriz. En yaygın ve etkili yöntemlerden biri, dizilerin sonundan başlayarak karşılaştırma yaparak birleştirmeyi gerçekleştirmektir. Bu yöntem, özellikle büyük diziler için daha verimlidir. Öncelikle, nums1 dizisinin sonuna nums2 dizisinin elemanlarını kopyalarız. Ardından, dizilerin son elemanlarından başlayarak, büyük olanı nums1 dizisinin ilgili konumuna yerleştiririz. Bu işlemi, nums2 dizisinin tüm elemanları işlenene kadar tekrar ederiz. Sonuç olarak, tamamen sıralı bir nums1 dizisi elde ederiz.
Java Kod Örneği
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1; // nums1'in son elemanının indeksi
int p2 = n - 1; // nums2'nin son elemanının indeksi
int p = m + n - 1; // nums1'in yeni son elemanının indeksi
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--];
} else {
nums1[p--] = nums2[p2--];
}
}
// nums2'deki kalan elemanları kopyala
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
Bu kod, öncelikle üç işaretçi kullanır: p1, p2 ve p. p1 ve p2, sırasıyla nums1 ve nums2 dizilerinin son elemanlarını işaret ederken, p, nums1 dizisinin birleştirilmiş son elemanını işaret eder. Kod, nums1 ve nums2 dizilerinin son elemanlarını karşılaştırarak, büyük olanı nums1 dizisinin sonuna yerleştirir. nums2 dizisinin elemanları bittiğinde, kalan nums1 elemanlarını kopyalamak için System.arraycopy() metodu kullanılır.
Performans Analizi
Bu çözümün zaman karmaşıklığı O(m+n) olup, oldukça verimlidir. Çünkü her bir elemanı en fazla bir kez karşılaştırır ve yer değiştirir. Uzay karmaşıklığı ise O(1)’dir, çünkü ekstra bir dizi kullanılmaz. Bu yöntem, büyük boyutlu diziler için bile performans sorununa yol açmaz.
Sonuç
Bu makalede, LeetCode’un “Sıralı Dizi Birleştirme” problemini Java ile çözmenin etkili bir yolunu inceledik. Verilen kod örneği, açık ve anlaşılır bir şekilde yazılmıştır ve performans açısından oldukça iyidir. Umarım bu makale, bu zorlu problemi anlamanıza ve çözmenize yardımcı olmuştur. Daha fazla algoritma ve veri yapısı çözümü için fatihsoysal.com adresini ziyaret edebilirsiniz. Ayrıca konuyla ilgili daha fazla bilgi edinmek için buraya tıklayabilirsiniz.
#Etiketler: LeetCode, Java, Sıralı Dizi Birleştirme, Merge Sorted Array, algoritma, veri yapısı, programlama, çözüm, kod örneği, yazılım geliştirme, Java Kod Örneği, Performans Analizi