Tìm yếu tố phổ biến ở 2 mảng được sắp xếp

Question

thể trùng lặp:
The intersection of two sorted arrays

chúng ta có hai mảng được sắp xếp A và B, ngoài so sánh một với tất cả các yếu tố trong mảng khác, làm thế nào để thiết kế một thuật toán tốt nhất để tìm mảng với các yếu tố chung của chúng?

Answer 1

Giữ hai con trỏ: một con trỏ cho mỗi mảng.

i <- 0, j <- 0 
repeat while i < length(arr1) and j < length(arr2): 
    if arr1[i] > arr2[j]: increase j 
    else if arr1[i] < arr2[j]: increase i 
    else : output arr[i], increase both pointers 

Ý tưởng là, nếu các dữ liệu được sắp xếp, nếu yếu tố này là "quá lớn" trong một mảng, nó sẽ là "quá lớn" cho tất cả các yếu tố khác còn lại trong mảng - kể từ khi nó được sắp xếp.

Giải pháp này yêu cầu phải truyền tải một lần trên dữ liệu. O(n) (với các hằng số tốt).

Answer 2

ngoài so sánh một với tất cả các yếu tố trong mảng khác

Bạn sẽ phải so sánh A [] đến B [] để biết rằng họ đều giống nhau - trừ khi bạn biết rất nhiều về loại dữ liệu nào họ có thể giữ. Bản chất của so sánh có thể có nhiều giải pháp và có thể được tối ưu hóa theo yêu cầu.

Nếu mảng được tạo đúng nghĩa là chỉ các giá trị tuần tự của mẫu đã biết và luôn bắt đầu từ điểm đã biết, bạn có thể xem chiều dài của từng mảng và biết có hay không tất cả các mục là phổ biến.

này tiếc là không âm thanh như một mảng rất thực tế hoặc hữu ích và do đó bạn đang trở lại để kiểm tra A [i] trong B []

Answer 3

Nếu độ dài của hai mảng (nói, A có N yếu tố và B có các thành phần M) tương tự nhau, thì cách tốt nhất là thực hiện tìm kiếm tuyến tính một phần tử của mảng trong một mảng khác. Tất nhiên, kể từ khi mảng được sắp xếp, tìm kiếm tiếp theo sẽ bắt đầu khi tìm kiếm trước đó đã dừng. Đây là nguyên tắc cổ điển được sử dụng trong thuật toán "sắp xếp mảng được sắp xếp". Mức độ phức tạp trên O(N + M).

Nếu độ dài khác nhau đáng kể (ví dụ: M << N), thì cách tiếp cận tối ưu hơn sẽ là lặp qua các phần tử của mảng ngắn hơn và sử dụng tìm kiếm nhị phân để tìm các giá trị này trong mảng dài hơn. Mức độ phức tạp là O(M * log N) trong trường hợp đó.

Như bạn có thể thấy O(M * log N) tốt hơn O(N + M) nếu M nhỏ hơn nhiều so với N và tệ hơn nữa.

Sự khác biệt về kích thước mảng sẽ kích hoạt chuyển đổi từ phương pháp này sang phương pháp khác phụ thuộc vào một số cân nhắc thực tế. Nếu được chọn dựa trên các thử nghiệm thực tế với dữ liệu của bạn.

Hai phương pháp này (tìm kiếm tuyến tính và nhị phân) có thể được "trộn" thành một thuật toán đơn. Giả sử M <= N. Trong trường hợp đó, hãy chọn bước giá trị S = [N/M].Bạn lấy phần tử đầu tiên từ mảng A và thực hiện tìm kiếm tuyến tính được sắp xếp theo chiều ngang cho phần tử đó trong mảng B với bước S, có nghĩa là bạn kiểm tra các phần tử B[0], B[S], B[2*S], B[3*S], ... và cứ tiếp tục như vậy. Khi bạn tìm thấy phạm vi chỉ mục [S*i, S*(i+1)] có khả năng chứa phần tử bạn đang tìm kiếm, bạn chuyển sang tìm kiếm nhị phân bên trong phân đoạn đó của mảng B. Làm xong. Tìm kiếm tuyến tính nằm ngang cho phần tử tiếp theo của A bắt đầu khi tìm kiếm trước đó bị tắt. (Là một lưu ý phụ, bạn nên chọn giá trị S bằng với công suất 2).

Thuật toán "được kết hợp" này là thuật toán tìm kiếm/hợp nhất tối ưu tiệm cận nhất cho hai mảng được sắp xếp tồn tại. Tuy nhiên, trong thực tế, cách tiếp cận đơn giản hơn với việc chọn tìm kiếm nhị phân hoặc tuyến tính tùy thuộc vào kích thước tương đối của các mảng hoạt động hoàn toàn tốt.