Apa itu Algoritma Squares of a Sorted Array?
Algoritma ini digunakan untuk mengolah array yang sudah terurut dan mengubahnya menjadi array baru dengan nilai kuadrat dari setiap elemen array asli. Proses ini dilakukan dengan cara yang efisien tanpa perlu mengurutkan array hasil kuadrat secara manual.
Strategi Algoritma
Strategi utama dari algoritma ini adalah menggunakan dua pointer, satu di awal array dan satu di akhir array. Kemudian, kita membandingkan nilai absolut dari elemen di kedua pointer tersebut dan meletakkan nilai kuadrat yang lebih besar di akhir array hasil.
Implementasi Algoritma
Implementasi algoritma ini dapat dilakukan dengan menggunakan bahasa pemrograman Python. Berikut adalah contoh kode implementasi:
class Solution:
def sortedSquares(self, nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
if abs(nums[left]) > abs(nums[right]):
result[pos] = nums[left] * nums[left]
left += 1
else:
result[pos] = nums[right] * nums[right]
right -= 1
pos -= 1
return result
Kelebihan Algoritma
Kelebihan dari algoritma ini adalah kita dapat mengolah array dengan waktu yang efisien, yaitu O(n), dan ruang yang digunakan juga O(n).
Kesimpulan
Algoritma Squares of a Sorted Array adalah salah satu contoh algoritma yang efisien dan efektif dalam mengolah array. Dengan menggunakan strategi dua pointer dan membandingkan nilai absolut, kita dapat menghasilkan array baru dengan nilai kuadrat dari setiap elemen array asli dengan waktu dan ruang yang efisien.
