Merge Sorted Array

Q: Độ phức tạp thời gian khi gộp hai mảng đã sắp xếp là bao nhiêu?

Dùng hai con trỏ, độ phức tạp là O(m + n) , trong đó m và n là độ dài của hai mảng: mỗi bước đặt một giá trị. Nối hai mảng rồi sắp xếp có độ phức tạp O((m + n) log(m + n)) .

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

+10

Bạn có hai mảng số nguyên, nums1 và nums2. Mỗi mảng đã được sắp xếp theo thứ tự không giảm. Hãy trả về một mảng duy nhất chứa mọi giá trị từ cả hai mảng, cũng theo thứ tự không giảm. Giá trị xuất hiện trong cả hai mảng sẽ xuất hiện trong kết quả với số lần bằng tổng số lần nó xuất hiện trong hai mảng.

Hàm

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: mảng đã sắp xếp thứ nhất
nums2integer-array: mảng đã sắp xếp thứ hai
Trả vềinteger-array: mọi giá trị của cả hai mảng trong một mảng đã sắp xếp, có độ dài nums1.length + nums2.length

Ràng buộc

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 và nums2 đều được sắp xếp theo thứ tự không giảm.

Ví dụ

Đầu vào: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Đầu ra: [1, 2, 3, 4, 9, 10]
Giải thích: Đọc hai phần tử đầu tiên và giữ lại phần tử nhỏ hơn: 1, rồi đến 2 và 3 từ nums2, tiếp theo là 4 và 9 từ nums1, cuối cùng là 10. Kết quả chứa đủ cả sáu giá trị.

Đầu vào: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Đầu ra: [-5, 0, 0, 0, 6, 8]
Giải thích: Số 0 xuất hiện hai lần trong nums1 và một lần trong nums2, nên kết quả có ba số 0. Số -5 nhỏ hơn mọi số trong nums2 và đứng đầu.

Câu hỏi mở rộng

Bạn có thể gộp k mảng đã sắp xếp, chứa tổng cộng N giá trị, trong thời gian O(N log k) 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

Cả hai mảng đều đã được sắp xếp, nên giá trị nhỏ nhất còn lại luôn nằm ở đầu một trong hai mảng. Hãy giữ một chỉ số cho mỗi mảng, chọn giá trị nhỏ hơn ở đầu mảng mỗi lần, rồi chỉ cần duyệt một lượt để tạo kết quả. Đây là bước trộn trong thuật toán sắp xếp trộn.

Ghép lại và sắp xếp

Ý tưởng

Gộp hai mảng rồi sắp xếp kết quả. Kết quả chứa mỗi giá trị đúng số lần giá trị đó xuất hiện, theo thứ tự. Với m giá trị trong nums1 và n giá trị trong nums2, việc sắp xếp có độ phức tạp O((m + n) log(m + n)). Tốc độ này đủ nhanh với các giới hạn này, nhưng cách làm đó bỏ qua thứ tự đã sắp xếp mà bạn được cung cấp.

Thuật toán

Tạo một mảng gồm các giá trị của nums1, tiếp theo là các giá trị của nums2.
Sắp xếp mảng theo thứ tự số tăng dần.
Trả về mảng.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Hai con trỏ, mỗi con trỏ cho một mảng

Ý tưởng

Các chỉ số i và j đánh dấu giá trị đầu tiên chưa dùng của mỗi mảng (array). Thêm giá trị nhỏ hơn trong nums1[i] và nums2[j], rồi tăng chỉ số tương ứng. Khi một mảng đã dùng hết, các giá trị còn lại của mảng kia đã đúng thứ tự, nên cứ thêm chúng vào cuối.

Mỗi bước ghi một giá trị, nên vòng lặp chạy m + n lần: độ phức tạp thời gian O(m + n), với kết quả là phần bộ nhớ bổ sung duy nhất.

Thuật toán

Đặt i và j thành 0, rồi tạo một kết quả rỗng.
Khi cả hai mảng vẫn còn phần tử, hãy so sánh nums1[i] với nums2[j].
Thêm phần tử nhỏ hơn vào kết quả rồi tăng chỉ số tương ứng. Nếu hai phần tử bằng nhau, chọn nums1[i].
Khi một mảng hết phần tử, thêm các phần tử còn lại của mảng kia.
Trả về kết quả.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

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

Dừng khi một mảng đã dùng hết và quên phần còn lại của mảng kia. Với [1, 2, 3] và [4, 5, 6], vòng lặp kết thúc sau 1, 2 và 3, còn 4, 5, 6 vẫn cần được sao chép.
Đọc nums1[i] sau khi i đã đến cuối. Kiểm tra cả hai chỉ số trước khi so sánh.
Bỏ mất các phần tử trùng lặp. [0, 0] và [0] được gộp thành [0, 0, 0], không phải [0].
Trong JavaScript và TypeScript, sort() không có hàm so sánh sẽ sắp xếp số dưới dạng văn bản, vì vậy [-5, 10, 9] vẫn giữ nguyên là [-5, 10, 9]. Truyền (a, b) => a - b.

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

Độ phức tạp thời gian khi gộp hai mảng đã sắp xếp là bao nhiêu?

Dùng hai con trỏ, độ phức tạp là O(m + n), trong đó m và n là độ dài của hai mảng: mỗi bước đặt một giá trị. Nối hai mảng rồi sắp xếp có độ phức tạp O((m + n) log(m + n)).

Làm thế nào để gộp hai mảng đã sắp xếp ngay tại chỗ?

Khi mảng đầu tiên còn chỗ ở cuối để chứa cả hai mảng, hãy điền từ phía sau. So sánh các giá trị lớn nhất còn lại của hai mảng, ghi giá trị lớn hơn vào ô trống cuối cùng rồi lùi sang trái. Điền từ phía sau sẽ không bao giờ ghi đè lên giá trị nào của mảng đầu tiên chưa được đặt.

Gộp hai mảng đã sắp xếp có giống với bước gộp trong thuật toán merge sort không?

Đúng vậy. Merge sort chia mảng thành hai nửa, sắp xếp từng nửa, rồi ghép hai nửa đã sắp xếp bằng đúng vòng lặp hai con trỏ này. Khi hai giá trị bằng nhau, lấy giá trị bên trái sẽ giữ nguyên thứ tự ban đầu của các giá trị bằng nhau, nhờ đó merge sort là thuật toán sắp xếp ổn định.

def merge(nums1, nums2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Đầu ra mong đợi

[1, 2, 3, 4, 9, 10]