Squares of a Sorted Array
Negatif değerler içerebilen, azalmayan sırada sıralanmış bir tam sayı dizisi nums alıyorsun. Her değerin karesini al ve kareleri, yine azalmayan sırada sıralanmış yeni bir dizi olarak döndür.
Fonksiyon
- numsinteger-array
- sıralanmış tamsayı dizisi, negatif değerlere izin verilir
- Döndürürinteger-array
- her değerin karesi, artmayan sırada
Kısıtlar
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsazalmayan sırada sıralanmıştır.
Örnekler
- Girdi
- nums = [-6, -2, 1, 3, 7]
- Çıktı
- [1, 4, 9, 36, 49]
- Açıklama
- Orijinal sıradaki kareler 36, 4, 1, 9 ve 49'dur. Negatif değerler -6 ve -2 büyük kareler verir, bu nedenle sıralama 36'yı sona yaklaştırır:
[1, 4, 9, 36, 49].
- Girdi
- nums = [-9, -4, -1]
- Çıktı
- [1, 16, 81]
- Açıklama
- Her değer negatiftir, bu yüzden kareler ters sırada çıkar: 81, 16, 1,
[1, 16, 81]olur.
Gönderirken +14 gizli test
Ek soru
Kare alma ve sıralama O(n log n) sürer. Bunu O(n) içinde yapabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
[-6, -2, 1, 3, 7]dizisinin karesini elle alın. Dizinin hangi kısmı sırasını kaybeder ve neden?En büyük kare her zaman
numsdeğerinin ilk değerinden veya son değerinden gelir, çünkü bu iki değer 0'a en uzak olanlardır.Her iki uca birer işaretçi koy. İki kareyi karşılaştır, büyük olanı sonucun arkasına yaz ve o işaretçiyi içeri doğru hareket ettir. Tüm konumlar doldurulana kadar tekrarla.
Çözüm
Karesini almak negatif olmayan değerlerin sırasını korur, ancak negatif değerlerin sırasını tersine çevirir; bu yüzden kareler sıralı değildir. Onları yeniden sıralamak işe yarar, ancak size verilen sıralamayı göz ardı eder. Önemli nokta şu: En büyük kare her zaman nums dizisinin iki ucundan birinden gelir. İki ucu karşılaştırın, daha büyük kareyi sonucun en arkasına yerleştirin ve ortaya doğru ilerleyin.
Karesini al, sonra sırala
Sezgi
Her değerin karesini alarak yeni bir dizi oluştur, ardından sırala. Kareler asla negatif olmaz ve sıralama, değerler nereden gelmiş olursa olsun onları sıraya dizer.
[-6, -2, 1, 3, 7] için kareler [36, 4, 1, 9, 49] olur ve sıralama [1, 4, 9, 36, 49] sonucunu verir.
Sıralamanın maliyeti O(n log n) olur. Burada yeterince hızlıdır, ancak girdiyi hiç sırası yokmuş gibi ele alır. Sonraki yaklaşım sıralamayı kullanır ve tek geçiş gerektirir.
Algoritma
numsiçindeki herxiçinx * xiçeren bir dizi oluştur.- Diziyi artan sayısal sıraya göre sırala.
- Diziyi döndür.
def sortedSquares(nums):
return sorted(x * x for x in nums)İki uçtan iki işaretçi
Sezgi
Kareleri, 0'dan olan uzaklığın karesi olarak düşün. Sıralı bir dizide 0'a en uzak değerler iki uçta bulunur: en negatif değer solda, en pozitif değer ise sağda. Bu yüzden en büyük kare nums[left]² ya da nums[right]² olur; aradaki hiçbir değer değil.
left değerini 0'da, right değerini n-1'de tut ve sonucu son konumundan geriye doğru doldur. Her adımda iki uçtaki kareleri karşılaştır, büyük olanı mevcut konuma yaz ve ilgili işaretçiyi içeri doğru ilerlet. İşaretçiler arasında kalanlar da yine sıralı bir dizi oluşturur; dolayısıyla aynı kural her adımda geçerlidir.
[-6, -2, 1, 3, 7] dizisinde: 49, 36'dan büyüktür ve sona yerleşir. Sonra 36, 9'dan; 9, 4'ten; 4, 1'den büyüktür ve 1, 0. konumu doldurur. Sonuç [1, 4, 9, 36, 49] olur. Her değer bir kez yerleştirilir: O(n) zaman ve ek dizi olarak yalnızca sonuç dizisi gerekir.
Algoritma
nuzunluğunda bir sonuç dizisi oluştur.leftdeğerini 0,rightdeğerinin-1olarak ayarla.poskonumunun-1’den 0’a kadar geriye doğru ilerlet.nums[left]²ilenums[right]²değerlerini karşılaştır.- Büyük olan kareyi
poskonumuna yaz ve ilgili işaretçiyi bir adım içeri doğru ilerlet. - Sonucu döndür.
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
Tuzaklar ve uç durumlar
İki işaretçili sürüm kısadır, ancak birkaç ayrıntı onu bozabilir.
- Sonucu baştan doldurmak. En küçük kare, değerlerin 0'ı kestiği yerde bulunur; bu nokta ortalarda herhangi bir yerde olabilir. Uçlar yalnızca en büyük kareyi gösterir. Sondan doldurun.
nums[left]ilenums[right]değerlerini kareleriyle veya mutlak değerleriyle karşılaştırmak yerine doğrudan karşılaştırmak. -6, 3'ten küçüktür, ancak karesi daha büyüktür.leftilerightkarşılaştığında durmak. Eşit olduklarında bir değer hâlâ yerleştirilmemiştir; sonucun her konumu üzerinde döngü kurun veyaleft <= rightkullanın.- Tüm girdilerin negatif veya tümünün pozitif olması.
[-9, -4, -1]için tüm işi sol işaretçi yapar,[2, 5, 8]içinse sağ işaretçi yapar. Her iki durumda da sıralı çıktı elde edilmelidir. - JavaScript ve TypeScript'te, karşılaştırıcı olmadan kullanılan
sort()sayıları metin olarak sıralar; bu nedenle[1, 4, 36, 9],[1, 36, 4, 9]olur.(a, b) => a - biletin.
Sıkça sorulan sorular4
Sıralı Bir Dizinin Karelerinin zaman karmaşıklığı nedir?
İki işaretçili çözüm O(n) zamanda çalışır: her değer bir kez karesini alır ve yerleştirilir. Karesini alıp ardından sıralamak O(n log n) maliyetindedir. Her iki yöntem de sonuç için O(n) bellek kullanır.
En büyük kare neden iki uçtan birinden gelir?
Bir sayının karesi, 0'dan uzaklığı arttıkça büyür. Sıralı bir dizide 0'ın en uzağındaki negatif değer ilk, pozitif değer ise son değerdir. Aradaki her değer 0'a bunlardan birinden daha yakın olduğundan, karesi en büyük olamaz.
Sonucu bunun yerine baştan doldurabilir misin?
Evet, ancak önce değerlerin 0'ı nerede geçtiğini bulman gerekir; örneğin ikili aramayla. Ardından iki işaretçi, iki sıralı listeyi birleştirir gibi bu noktadan dışa doğru ilerler: negatifler sağdan sola, negatif olmayanlar soldan sağa okunur. Sondan doldurmak arama ihtiyacını ortadan kaldırır, çünkü uçlar en baştan bellidir.
Karelerin Sıralanmış Dizisi bir birleştirme problemi midir?
Kılık değiştirmiş hâliyle, evet. Negatif değerlerin kareleri bir sıralı liste oluşturur (sağdan sola okunur), negatif olmayan değerlerin kareleri ise başka bir liste oluşturur. Bunları birleştirmek, birleştirmeli sıralamanın birleştirme adımıdır; bu nedenle tek bir doğrusal geçişte tamamlanabilir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def sortedSquares(nums):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
nums = [-6, -2, 1, 3, 7]
Beklenen
[1, 4, 9, 36, 49]