Chương trình tìm mảng bình phương đã sắp xếp Python

Cho mảng nums đã sắp xếp tăng dần. Bình phương từng phần tử và trả về mảng kết quả cũng sắp xếp tăng dần.

Ví dụ: nums=[-8,-3,0,5,6] → [0,9,25,36,64].

Giải thuật (Hai con trỏ từ hai đầu)

1. l=0 (đầu), r=n-1 (cuối), index=n-1 (vị trí ghi kết quả)
2. So sánh |nums[l]| và |nums[r]|:
   • Nếu bên trái lớn hơn: res[index] = nums[l]², l++
   • Ngược lại: res[index] = nums[r]², r--
3. index--, lặp cho đến index < 0

Ví dụ triển khai

def solve(nums):
    n = len(nums)
    l, r = 0, n - 1
    index = n - 1
    res = [0] * n
    while index >= 0:
        if abs(nums[l]) > abs(nums[r]):
            res[index] = nums[l] * nums[l]
            l += 1
        else:
            res[index] = nums[r] * nums[r]
            r -= 1
        index -= 1
    return res

print(solve([-8, -3, 0, 5, 6]))

Đầu vào

[-8, -3, 0, 5, 6]

Đầu ra

[0, 9, 25, 36, 64]