Squares of a Sorted Array

Q: Độ phức tạp thời gian của bài toán Bình phương của một mảng đã sắp xếp là bao nhiêu?

Giải pháp hai con trỏ chạy trong thời gian O(n) : mỗi giá trị được bình phương và đưa vào một lần. Bình phương rồi sắp xếp tốn O(n log n) . Cả hai đều dùng O(n) bộ nhớ cho kết quả.

DễHai con trỏ Sắp xếp

+10

Bạn được cung cấp một mảng số nguyên nums đã sắp xếp theo thứ tự không giảm. Mảng có thể chứa các giá trị âm. Bình phương từng giá trị rồi trả về một mảng mới chứa các bình phương, cũng được sắp xếp theo thứ tự không giảm.

Hàm

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: mảng số nguyên đã sắp xếp, có thể chứa số âm
Trả vềinteger-array: bình phương của mỗi giá trị, được sắp xếp theo thứ tự không giảm

Ràng buộc

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums được sắp xếp theo thứ tự không giảm.

Ví dụ

Đầu vào: nums = [-6, -2, 1, 3, 7]
Đầu ra: [1, 4, 9, 36, 49]
Giải thích: Các bình phương theo thứ tự ban đầu là 36, 4, 1, 9 và 49. Các giá trị âm -6 và -2 tạo ra bình phương lớn, nên việc sắp xếp chuyển 36 về gần cuối: [1, 4, 9, 36, 49].

Đầu vào: nums = [-9, -4, -1]
Đầu ra: [1, 16, 81]
Giải thích: Mọi giá trị đều âm, nên các bình phương xuất hiện theo thứ tự ngược lại: 81, 16, 1 trở thành [1, 16, 81].

Câu hỏi mở rộng

Bình phương và sắp xếp mất O(n log n). Bạn có thể làm việc đó trong O(n) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Phép bình phương đảo ngược thứ tự của các giá trị âm, vì vậy các bình phương không được sắp xếp theo thứ tự. Nhưng bình phương lớn nhất luôn xuất phát từ một trong hai đầu của nums. Hãy so sánh hai đầu, đặt bình phương lớn hơn vào cuối kết quả rồi tiến dần vào giữa.

Bình phương rồi sắp xếp

Ý tưởng

Tạo một mảng mới chứa bình phương của từng giá trị, sau đó sắp xếp mảng đó. Việc sắp xếp đưa các bình phương về đúng thứ tự, bất kể chúng xuất phát từ đâu. Sắp xếp có độ phức tạp O(n log n) và bỏ qua thứ tự ban đầu.

Thuật toán

Tạo một mảng gồm x * x cho mỗi x trong nums.
Sắp xếp mảng theo thứ tự số tăng dần rồi trả về.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Hai con trỏ từ hai đầu

Ý tưởng

Bình phương tăng theo khoảng cách đến 0. Trong một mảng đã sắp xếp, các giá trị xa 0 nhất nằm ở hai đầu, giá trị âm nhất ở bên trái và giá trị dương nhất ở bên phải, vì vậy bình phương lớn nhất là nums[left]² hoặc nums[right]². Ghi giá trị lớn hơn vào cuối mảng kết quả rồi dịch con trỏ đó vào trong. Phần còn lại giữa hai con trỏ vẫn được sắp xếp, nên điều tương tự đúng ở mỗi bước.

Với [-6, -2, 1, 3, 7]: 49 lớn hơn 36 nên được ghi vào cuối. Sau đó 36 lớn hơn 9, 9 lớn hơn 4, 4 lớn hơn 1, và số 1 lấp vào vị trí 0. Mỗi giá trị được đặt đúng một lần: thời gian O(n), và mảng kết quả là mảng bổ sung duy nhất.

Thuật toán

Tạo một mảng kết quả có độ dài n. Đặt left thành 0 và right thành n-1.
Duyệt vị trí pos từ n-1 giảm dần đến 0.
So sánh nums[left]² với nums[right]².
Ghi bình phương lớn hơn vào pos rồi dịch con trỏ đó vào trong một bước.
Trả về kết quả.

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

Lỗi thường gặp và trường hợp biên

Điền kết quả từ đầu. Bình phương nhỏ nhất nằm ở vị trí các giá trị đổi dấu qua 0, vị trí này có thể nằm ở bất kỳ đâu giữa mảng; hai đầu chỉ cho biết giá trị lớn nhất.
So sánh nums[left] với nums[right] thay vì bình phương của chúng. -6 nhỏ hơn 3, nhưng bình phương của nó lớn hơn, nên [-6, 3] cho kết quả [36, 9].
Dừng khi left gặp right. Vẫn còn một giá trị chưa được đặt vào kết quả; hãy lặp qua mọi vị trí hoặc dùng left <= right.
Trong JavaScript và TypeScript, sort() không có hàm so sánh sẽ sắp xếp các số dưới dạng văn bản, nên [1, 4, 36, 9] trở thành [1, 36, 4, 9]. Hãy truyền (a, b) => a - b.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Bình phương của một mảng đã sắp xếp là bao nhiêu?

Giải pháp hai con trỏ chạy trong thời gian O(n): mỗi giá trị được bình phương và đưa vào một lần. Bình phương rồi sắp xếp tốn O(n log n). Cả hai đều dùng O(n) bộ nhớ cho kết quả.

Bạn có thể điền kết quả từ phía trước thay vào đó không?

Đúng, nhưng trước tiên bạn phải tìm vị trí các giá trị đổi dấu qua 0, chẳng hạn bằng cách tìm kiếm nhị phân. Sau đó, hai con trỏ di chuyển ra ngoài từ điểm đó. Điền từ cuối về trước giúp tránh phải tìm kiếm, vì ta biết vị trí hai đầu ngay từ đầu.

Squares of a Sorted Array có phải là một bài toán trộn không?

Các giá trị âm sau khi bình phương, đọc từ phải sang trái, tạo thành một danh sách đã sắp xếp; các giá trị không âm sau khi bình phương tạo thành một danh sách khác. Gộp chúng lại là bước trộn của thuật toán sắp xếp trộn, vì vậy việc này chỉ cần một lượt duyệt tuyến tính.

def sortedSquares(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [-6, -2, 1, 3, 7]

Đầu ra mong đợi

[1, 4, 9, 36, 49]