Count Inversions

Q: Thứ tự đảo ngược trong mảng là gì?

Nghịch thế là một cặp vị trí i < j sao cho nums[i] > nums[j] , nghĩa là một giá trị lớn hơn đứng trước một giá trị nhỏ hơn. Danh sách đã sắp xếp có 0 nghịch thế, còn danh sách đảo ngược gồm các giá trị khác nhau có nhiều nghịch thế nhất, n(n-1)/2 . Số nghịch thế bằng số lần đổi chỗ hai phần tử kề nhau mà bubble sort thực hiện.

Q: Độ phức tạp thời gian của việc đếm số nghịch thế bằng merge sort là bao nhiêu?

Thời gian O(n log n) và bộ nhớ phụ O(n) cho bộ đệm trộn. Mỗi cấp trong log n cấp trộn đều xử lý mỗi giá trị một lần, tổng cộng khoảng 3 × 10^5 bước với 2 × 10^4 giá trị. Vòng lặp xét từng cặp có độ phức tạp O(n²) .

Trung bìnhSắp xếp Đệ quy

+10

Cho một danh sách số nguyên nums, hãy trả về số lượng nghịch thế: các cặp chỉ số i < j sao cho nums[i] > nums[j], tức là một giá trị lớn hơn đứng trước một giá trị nhỏ hơn. Các giá trị bằng nhau không bao giờ tạo thành nghịch thế, và một danh sách đã sắp xếp thì không có nghịch thế nào.

Hàm

countInversions(nums: integer-array) → integer

numsinteger-array: danh sách số nguyên
Trả vềinteger: số cặp i < j thỏa mãn nums[i] > nums[j]

Ràng buộc

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Đáp án có giá trị tối đa là n(n-1)/2 < 2 × 10⁸, nên có thể biểu diễn bằng số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: nums = [5, 3, 8, 1, 4]
Đầu ra: 6
Giải thích: 5 đứng trước 3, 1 và 4: 3 cặp. 3 đứng trước 1, và 8 đứng trước 1 và 4: thêm 3 cặp. 1 và 4 đúng thứ tự, vậy tổng cộng là 6.

Câu hỏi mở rộng

Nếu một cặp chỉ được tính khi nums[i] > 2 × nums[j], thì điều gì thay đổi? Merge sort vẫn có thể đếm những cặp đó trong O(n log n) không?

Lời giải

Kiểm tra từng cặp cần khoảng n² / 2 phép so sánh. Merge sort đếm hàng loạt các cặp: khi một giá trị từ nửa bên phải được đưa vào trong lúc trộn, mọi giá trị bên trái còn đang chờ đều lớn hơn và đứng trước nó. Một phép trừ đếm cả nhóm đó, vì vậy việc đếm không tốn thêm gì ngoài bước sắp xếp O(n log n).

Kiểm tra từng cặp

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi chỉ số i, kiểm tra từng chỉ số j đứng sau và cộng 1 khi nums[i] > nums[j]. Đó là định nghĩa, và phép so sánh nghiêm ngặt loại các giá trị bằng nhau.

Chi phí là n(n-1)/2 phép so sánh: gần bằng 2 × 10^8 với 2 × 10^4 giá trị, và tăng gấp đôi n khiến chi phí tăng gấp bốn lần.

Thuật toán

Đặt count = 0.
Với mỗi i từ 0 đến n-1, và mỗi j từ i + 1 đến n-1, cộng 1 vào count khi nums[i] > nums[j].
Trả về count.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Sắp xếp trộn có đếm trong khi trộn

Ý tưởng

Chia danh sách ở giữa. Một cặp nghịch thế có cả hai giá trị ở nửa trái, cả hai ở nửa phải hoặc mỗi giá trị ở một bên. Gọi đệ quy trên từng nửa sẽ đếm hai loại đầu tiên và sắp xếp nửa đó. Việc sắp xếp chỉ di chuyển các giá trị trong cùng một nửa, nên mọi giá trị ở nửa trái vẫn đứng trước mọi giá trị ở nửa phải, và các cặp băng qua hai nửa không thay đổi.

Khi trộn, nếu left[i] ≤ right[j], hãy đặt left[i]: mọi giá trị bên phải còn chờ đều lớn hơn hoặc bằng right[j], nên không tạo thành cặp nghịch thế nào. Nếu không, right[j] nhỏ hơn left[i] và, vì nửa trái đã được sắp xếp, nhỏ hơn mọi giá trị bên trái còn chờ. Cộng số lượng các giá trị đó. Khi hai giá trị bằng nhau, đặt giá trị bên trái trước để các giá trị bằng nhau không tạo thành cặp nghịch thế.

Với [5, 3, 8, 1, 4], hai nửa có lần lượt 1 và 2 cặp nghịch thế. Khi trộn [3, 5] với [1, 4, 8], 1 đi qua 3 và 5, còn 4 đi qua 5: 1 + 2 + 3 = 6.

Thuật toán

Sao chép nums và tạo một vùng đệm có cùng độ dài.
Để sắp xếp và đếm một khoảng có ít hơn 2 giá trị, hãy trả về 0.
Nếu không, hãy chia khoảng đó tại mid, rồi sắp xếp và đếm từng nửa.
Gộp hai nửa qua vùng đệm: nếu left[i] ≤ right[j], lấy giá trị bên trái; nếu không, lấy giá trị bên phải và cộng số giá trị bên trái chưa được đưa vào.
Sao chép khoảng đã gộp trở lại và trả về tổng của ba số đếm.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

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

Cộng 1 khi đặt một giá trị bên phải. Giá trị đó vượt qua tất cả giá trị bên trái còn đang chờ, vì vậy hãy cộng số lượng của chúng, mid - i.
Lấy giá trị bên phải khi hòa, với left[i] < right[j] làm điều kiện kiểm tra phía bên trái. Khi đó, [2, 2, 2, 1] đếm các số 2 bằng nhau với nhau và trả về kết quả lớn hơn 3. Hãy dùng ≤.
Đếm khi sao chép các giá trị còn lại sau khi một nửa đã hết. Các giá trị bên trái còn lại không có giá trị bên phải nào đứng sau chúng, còn các giá trị bên phải còn lại đã được so sánh với mọi giá trị bên trái.

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

Thứ tự đảo ngược trong mảng là gì?

Nghịch thế là một cặp vị trí i < j sao cho nums[i] > nums[j], nghĩa là một giá trị lớn hơn đứng trước một giá trị nhỏ hơn. Danh sách đã sắp xếp có 0 nghịch thế, còn danh sách đảo ngược gồm các giá trị khác nhau có nhiều nghịch thế nhất, n(n-1)/2. Số nghịch thế bằng số lần đổi chỗ hai phần tử kề nhau mà bubble sort thực hiện.

Độ phức tạp thời gian của việc đếm số nghịch thế bằng merge sort là bao nhiêu?

Thời gian O(n log n) và bộ nhớ phụ O(n) cho bộ đệm trộn. Mỗi cấp trong log n cấp trộn đều xử lý mỗi giá trị một lần, tổng cộng khoảng 3 × 10^5 bước với 2 × 10^4 giá trị. Vòng lặp xét từng cặp có độ phức tạp O(n²).

Có thể đếm số nghịch thế mà không cần sắp xếp trộn không?

Có. Cây Fenwick (cây chỉ số nhị phân) trên thứ hạng của các giá trị duyệt qua danh sách một lần và với mỗi giá trị, đếm xem có bao nhiêu giá trị trước đó lớn hơn, với độ phức tạp O(log n) cho mỗi giá trị. Tổng độ phức tạp cũng là O(n log n). Cây tìm kiếm cân bằng theo dõi kích thước các cây con cũng hoạt động tương tự.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [5, 3, 8, 1, 4]

Đầu ra mong đợi