Làm cách nào để tìm số lần đảo ngược trong một mảng?

Question

thể trùng lặp:
Counting inversions in an array

Đây là một phone interview question: "Tìm số đảo trong một mảng". Tôi đoán họ có nghĩa là giải pháp O (N log N). Tôi tin rằng nó không thể tốt hơn O (N log N) vì đây là sự phức tạp phân loại.

Câu trả lời cho một similar question có thể được tóm tắt như sau:

1. Tính nửa khoảng cách các yếu tố cần được di chuyển để sắp xếp mảng: sao chép mảng và sắp xếp các bản sao. Đối với mỗi phần tử của mảng gốc a[i], hãy tìm vị trí của nó j trong bản sao đã sắp xếp (tìm kiếm nhị phân) và tính tổng một nửa khoảng cách abs(i - j)/2.

2. Sửa đổi merge sort: sửa đổi merge để đếm đảo ngược giữa hai mảng được sắp xếp và chạy thường xuyên merge sort với sửa đổi merge.

   Có hợp lý không? Có giải pháp nào khác (có thể đơn giản hơn) không? Không phải là quá khó khăn cho một cuộc phỏng vấn qua điện thoại sao?

Answer 1

Nó thực sự là một ứng dụng của thuật toán phân chia và chinh phục, và nếu bạn quen thuộc với nó, bạn có thể đưa ra giải pháp một cách nhanh chóng.

Lấy [1 3 8 5 7 2 4 6] làm ví dụ, giả sử chúng ta đã sắp xếp mảng là [1 3 5 8] và [2 4 6 7] và bây giờ chúng ta cần kết hợp hai mảng và nhận tổng số nghịch đảo.

Vì chúng tôi đã có số lần đảo ngược trong mỗi mảng phụ, chúng tôi chỉ cần tìm ra số lần đảo ngược do việc hợp nhất mảng gây ra. Mỗi lần một phần tử được chèn vào, ví dụ, 2 được chèn vào [1 # 3 5 8], bạn có thể biết có bao nhiêu nghịch đảo giữa mảng đầu tiên và phần tử 2 (3 cặp trong ví dụ này). Sau đó, bạn có thể thêm chúng lên để nhận được số lần đảo ngược do việc hợp nhất.

Answer 2

Bạn cũng có thể sử dụng một cách tiếp cận đếm loại giống như, nếu mảng chỉ chứa số lượng nhỏ ví dụ (như nếu đó là một mảng ký tự):

inversions = 0 
let count = array of size array.Length 
for i = 0 to array.Length - 1 do 
    for j = array[i] + 1 to maxArrayValue do 
     inversions = inversions + count[j] 

    count[array[i]] = count[array[i]] + 1 

Về cơ bản, giữ một đếm bao nhiêu lần mỗi phần tử xuất hiện. Sau đó, tại mỗi bước i, số lần đảo ngược thành phần thứ i tạo bằng tổng của tất cả các phần tử lớn hơn i đến trước i, mà bạn có thể dễ dàng tính toán bằng số bạn đang giữ.

Đây sẽ là O(n*eps) trong đó eps là tên miền của các phần tử trong mảng của bạn.

Điều này chắc chắn đơn giản hơn theo ý kiến ​​của tôi. Đối với hiệu quả, nó chỉ tốt nếu eps là nhỏ rõ ràng. Nếu có, thì nó sẽ nhanh hơn các phương pháp khác vì không có đệ quy.