Làm thế nào tôi có thể xác định hiệu quả nếu hai danh sách chứa các phần tử được sắp xếp theo cùng một cách?

Question

Tôi có hai danh sách có cùng loại phần tử, mỗi danh sách có nhiều nhất một phần tử của mỗi giá trị (giả sử int và số duy nhất), nhưng nếu không có giới hạn (có thể là tập hợp con của phần tử kia, chúng có thể hoàn toàn rời rạc hoặc chia sẻ một số yếu tố nhưng không chia sẻ với người khác).

Làm cách nào để xác định hiệu quả liệu A có sắp xếp bất kỳ hai mục nào theo cách khác với B không? Ví dụ: nếu A có các mục 1, 2, 10 và B, các mục 2, 10, 1, thuộc tính sẽ không giữ dưới dạng Danh sách 1 trước 10 nhưng B liệt kê nó sau 10, 2, 10 so với 2, 10 , 5 sẽ là hoàn toàn hợp lệ tuy nhiên như A không bao giờ đề cập đến 5 ở tất cả, tôi không thể dựa vào bất kỳ quy tắc phân loại nhất định được chia sẻ bởi cả hai danh sách.

Answer 1

Bạn có thể nhận được O (n) như sau. Đầu tiên, tìm giao điểm của hai bộ sử dụng băm. Thứ hai, kiểm tra xem A và B có giống nhau không nếu bạn chỉ xem xét các yếu tố từ giao lộ.

Answer 2

cách tiếp cận của tôi sẽ được đầu tiên làm bản sao sắp xếp của A và B mà cũng ghi lại vị trí của các yếu tố trong danh sách ban đầu:

for i in 1 .. length(A): 
    Apos[i] = (A, i) 
sortedApos = sort(Apos[] by first element of each pair) 

for i in 1 .. length(B): 
    Bpos[i] = (B, i) 
sortedBpos = sort(Bpos[] by first element of each pair) 

Bây giờ tìm thấy những yếu tố chung sử dụng một hợp nhất danh sách tiêu chuẩn mà ghi lại vị trí ở cả hai A và B trong những yếu tố chia sẻ:

i = 1 
j = 1 
shared = [] 
while i <= length(A) && j <= length(B) 
    if sortedApos[i][1] < sortedBpos[j][1] 
     ++i 
    else if sortedApos[i][1] > sortedBpos[j][1] 
     ++j 
    else // They're equal 
     append(shared, (sortedApos[i][2], sortedBpos[j][2])) 
     ++i 
     ++j 

Cuối cùng, sắp xếp shared bởi yếu tố đầu tiên của nó (vị trí trong A) và kiểm tra xem tất cả các phần tử thứ hai của nó (vị trí trong B) đang tăng lên hay không. Đây sẽ là trường hợp khi và chỉ khi các yếu tố chung cho A và B xuất hiện trong cùng một thứ tự:

sortedShared = sort(shared[] by first element of each pair) 
for i = 2 .. length(sortedShared) 
    if sortedShared[i][2] < sortedShared[i-1][2] 
     return DIFFERENT 

return SAME 

Thời gian phức tạp: 2 * (O (n) + O (nlog n)) + O (n) + O (nlog n) + O (n) = O (nlog n).

Answer 3

Cách tiếp cận chung: lưu trữ tất cả các giá trị và vị trí của chúng trong B dưới dạng khóa và giá trị trong HashMap. Lặp lại các giá trị trong A và tìm chúng trong HashMap của B để lấy vị trí của chúng trong B (hoặc null). Nếu vị trí này là trước giá trị vị trí lớn nhất mà bạn đã thấy trước đó, thì bạn biết rằng thứ gì đó trong B theo thứ tự khác với A. Chạy trong thời gian O (n).

Rough, mã hoàn toàn chưa được kiểm tra:

boolean valuesInSameOrder(int[] A, int[] B) 
{ 
    Map<Integer, Integer> bMap = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < B.length; i++) 
    { 
    bMap.put(B[i], i); 
    } 

    int maxPosInB = 0; 
    for (int i = 0; i < A.length; i++) 
    { 
    if(bMap.containsKey(A[i])) 
    { 
     int currPosInB = bMap.get(A[i]); 
     if (currPosInB < maxPosInB) 
     { 
     // B has something in a different order than A 
     return false; 
     } 
     else 
     { 
     maxPosInB = currPosInB; 
     } 
    } 
    } 

    // All of B's values are in the same order as A 
    return true; 
}