Sıralı listenin kareleri
Görev tanımı
Problem
Bir tam sayı listesi azalmayan sırada sıralı ve negatif değerler içerebilir. Her değerin karesini tutan, yine azalmayan sırada yeni bir liste döndür. Kare alıp sonra sıralamak O(n log n) zaman alır; hedef, girdinin zaten sahip olduğu sırayı kullanarak O(n).
Örnekler
Input: nums = [-5, -2, 1, 3, 4]
Output: [1, 4, 9, 16, 25]
Neden: -5 en küçük değer ama en büyük kareyi veriyor
Input: nums = [-7, -3, -2]
Output: [4, 9, 49]
Neden: hepsi negatif, bu yüzden kareler ters sırada çıkıyor
Input: nums = []
Output: []
Neden: edge case: karesi alınacak bir şey yok
İpuçları
0 / 3
Kareler sıralarını kaybeder, çünkü büyük negatif değerler büyük karelere dönüşür. En büyük kare girdinin neresinden gelebilir?
En büyük kare her zaman girdinin iki ucundan birinden gelir. Bu, içe doğru ilerleyen iki pointer'ı ve arkadan doldurulan bir çıktıyı akla getirir.
Her uçta bir pointer ve son çıktı hücresinde bir yazma konumu tut. İki pointer'daki mutlak değerleri karşılaştır, büyük olanın karesini yaz, o pointer'ı içe kaydır ve her hücre dolana kadar yazma konumunu geri çek.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- nums is sorted in non-decreasing order
- values may be negative
- target O(n) time
Çözüm
En büyük mutlak değer sıralı girdinin her zaman bir ucundadır; bu yüzden henüz yazılmamış en büyük kare her zaman iki uç kareden biridir. İki pointer (işaretçi) uçlardan başlar, çıktı da son hücresinden geriye doğru doldurulur; iki sıralı diziyi birleştirirken kullanılan arkadan öne fikrinin aynısı. Her adım bir kare yazar ve bir pointer'ı kaydırır, yani döngü tam n kez döner. Zaman O(n), çıktı için alan O(n).
def sorted_squares(nums):
out = [0] * len(nums)
lo, hi = 0, len(nums) - 1
for write in range(len(nums) - 1, -1, -1): # fill from the back
if abs(nums[lo]) > abs(nums[hi]): # the bigger end gives the bigger square
out[write] = nums[lo] * nums[lo]
lo += 1
else:
out[write] = nums[hi] * nums[hi]
hi -= 1
return out
print(sorted_squares([-5, -2, 1, 3, 4])) # -> [1, 4, 9, 16, 25]
print(sorted_squares([-7, -3, -2])) # -> [4, 9, 49]
print(sorted_squares([])) # -> []Kodda değil de fikirde mi takıldın? Sıralı dizileri birleştirme bunu anlatıyor.