Tìm các phần tử phổ biến trong N mảng được sắp xếp không có khoảng trống thừa

Question

Cho các mảng N có sizeof N và tất cả đều được sắp xếp, nếu nó không cho phép bạn sử dụng thêm không gian, cách tìm dữ liệu chung một cách hiệu quả hoặc ít phức tạp hơn ?

Đối với ví dụ:

1. 10 160 200 500 500 
2. 4 150 160 170 500 
3. 2 160 200 202 203 
4. 3 150 155 160 300 
5. 3 150 155 160 301 

Đây là một câu hỏi phỏng vấn, tôi thấy một số câu hỏi mà là tương tự nhưng họ không bao gồm các điều kiện thêm đầu vào được sắp xếp hoặc không thể sử dụng thêm bộ nhớ.

Tôi không thể nghĩ ra bất kỳ giải pháp nào nhỏ hơn độ phức tạp O (n^2 lg n). Trong trường hợp đó, tôi muốn đi với các giải pháp đơn giản nhất mà mang lại cho tôi sự phức tạp này, đó là:

not_found_flag = false 

    for each element 'v' in row-1 
     for each row 'i' in the remaining set 
      perform binary search for 'v' in 'i' 
      if 'v' not found in row 'i' 
       not_found_flag = true 
       break 
     if not not_found_flag 
      print element 'v' as it is one of the common element 

Chúng ta có thể cải thiện điều này bằng cách so sánh min và max của mỗi hàng và quyết định trên cơ sở đó cho dù đó có thể cho một số 'num' nằm giữa 'min_num' và 'max_num' của hàng đó.

tìm kiếm nhị phân -> O (log n) Đối với tìm kiếm 1 num trong n-1 hàng: O (nlogn) Binary tìm kiếm mỗi số trong hàng đầu tiên: O (n2logn)

tôi chọn hàng đầu tiên , chúng tôi có thể chọn bất kỳ hàng nào và nếu không có phần tử nào của hàng được chọn được tìm thấy trong bất kỳ hàng nào (N-1) thì chúng tôi không thực sự có dữ liệu chung.

Answer 1

Có vẻ như điều này có thể được thực hiện trong O(n^2); tức là, chỉ cần nhìn từng phần tử một lần. Lưu ý rằng nếu một phần tử là phổ biến cho tất cả các mảng thì nó phải tồn tại trong bất kỳ phần tử nào trong số chúng. Ngoài ra cho các mục đích minh hoạ (và kể từ khi bạn sử dụng vòng lặp ở trên) tôi sẽ giả sử chúng ta có thể giữ một chỉ mục cho mỗi mảng, nhưng tôi sẽ nói về cách để làm được điều này sau này.

Hãy gọi các mảng A_1 qua A_N, và sử dụng các chỉ số bắt đầu từ 1. Mã giả:

# Initial index values set to first element of each array 
for i = 1 to N: 
    x_i = 1 

for x_1 = 1 to N: 
    val = A_1[x_1] 
    print_val = true 
    for i = 2 to N: 
    while A_i[x_i] < val: 
     x_i = x_i + 1 
    if A_i[x_i] != val: 
     print_val = false 
    if print_val: 
    print val 

Giải thích về thuật toán. Chúng tôi sử dụng mảng đầu tiên (hoặc bất kỳ mảng tùy ý) làm thuật toán tham chiếu, và lặp qua tất cả các mảng khác song song (loại giống như bước hợp nhất của một sắp xếp hợp nhất, ngoại trừ với mảng N.) Mỗi ​​giá trị của mảng tham chiếu đó là phổ biến cho tất cả các mảng phải có mặt trong tất cả các mảng khác. Vì vậy, đối với mỗi mảng khác (vì chúng được sắp xếp), chúng tôi tăng chỉ mục x_i cho đến khi giá trị tại chỉ mục đó A_i[x_i] ít nhất là giá trị mà chúng tôi đang tìm kiếm (chúng tôi không quan tâm đến giá trị thấp hơn;) Chúng ta có thể làm điều này vì các mảng được sắp xếp và do đó không phá hủy đơn điệu. Nếu tất cả các mảng có giá trị này, sau đó chúng ta in nó, nếu không chúng ta tăng x_1 trong mảng tham chiếu và tiếp tục đi. Chúng ta phải làm điều này ngay cả khi chúng ta không in giá trị.

Cuối cùng, chúng tôi đã in tất cả các giá trị chung cho tất cả các mảng, trong khi chỉ kiểm tra từng phần tử một lần.

Bắt đầu với yêu cầu bộ nhớ bổ sung. Có nhiều cách để làm điều này, nhưng tôi nghĩ cách dễ nhất là kiểm tra phần tử đầu tiên của mỗi mảng và lấy giá trị tối đa làm mảng tham chiếu A_1. Nếu chúng giống nhau, in giá trị đó, và sau đó lưu trữ các chỉ mục x_2 ... x_N làm phần tử đầu tiên của mỗi mảng.

thực hiện Java (cho ngắn gọn, nếu không có sự thêm hack), sử dụng ví dụ đầu vào của bạn:

public static void main(String[] args) { 
    int[][] a = { 
      { 10, 160, 200, 500, 500, }, 
      { 4, 150, 160, 170, 500, }, 
      { 2, 160, 200, 202, 203, }, 
      { 3, 150, 155, 160, 300 }, 
      { 3, 150, 155, 160, 301 } }; 

    int n = a.length; 
    int[] x = new int[n]; 

    for(; x[0] < n; x[0]++) { 
     int val = a[0][x[0]]; 
     boolean print = true; 
     for(int i = 1; i < n; i++) { 
      while (a[i][x[i]] < val && x[i] < n-1) x[i]++;    
      if (a[i][x[i]] != val) print = false;    
     } 
     if (print) System.out.println(val); 
    } 
} 

Output:

160 

Answer 2

Một O (n^2) (Python) phiên bản đó doesn không sử dụng thêm dung lượng, nhưng sửa đổi mảng ban đầu. Cho phép lưu trữ các phần tử phổ biến mà không cần in chúng:

data = [ 
    [10, 160, 200, 500, 500], 
    [4, 150, 160, 170, 500], 
    [2, 160, 200, 202, 203], 
    [3, 150, 155, 160, 300], 
    [3, 150, 155, 160, 301], 
] 

for k in xrange(len(data)-1): 
    A, B = data[k], data[k+1] 
    i, j, x = 0, 0, None 

    while i<len(A) or j<len(B): 
     while i<len(A) and (j>=len(B) or A[i] < B[j]): 
      A[i] = x 
      i += 1 

     while j<len(B) and (i>=len(A) or B[j] < A[i]): 
      B[j] = x 
      j += 1 

     if i<len(A) and j<len(B): 
      x = A[i] 
      i += 1 
      j += 1 

print data[-1] 

Thứ tôi đang làm là lấy tất cả các mảng trong phần tử, loại bỏ phần tử tiếp theo, loại bỏ những phần không phổ biến.

Answer 3

Đây là một giải pháp trong python O(n^2), sử dụng không gian phụ trợ nhưng phá hủy các danh sách:

def find_common(lists): 
    num_lists = len(lists) 
    first_list = lists[0] 
    for j in first_list[::-1]: 
     common_found = True 
     for i in range(1,num_lists): 
      curr_list = lists[i] 
      while curr_list[len(curr_list)-1] > j: 
       curr_list.pop() 
      if curr_list[len(curr_list)-1] != j: 
       common_found = False 
       break 
     if common_found: 
      return j 

Answer 4

Đây là việc thực hiện Java

public static Integer[] commonElementsInNSortedArrays(int[][] arrays) { 
    int baseIndex = 0, currentIndex = 0, totalMatchFound= 0; 
    int[] indices = new int[arrays.length - 1]; 
    boolean smallestArrayTraversed = false; 
    List<Integer> result = new ArrayList<Integer>(); 
    while (!smallestArrayTraversed && baseIndex < arrays[0].length) { 
     totalMatchFound = 0; 
     for (int array = 1; array < arrays.length; array++) { 
      currentIndex = indices[array - 1]; 
      while (currentIndex < arrays[array].length && arrays[array][currentIndex] < arrays[0][baseIndex]) { 
       currentIndex ++;      
      } 

      if (currentIndex < arrays[array].length) { 
       if (arrays[array][currentIndex] == arrays[0][baseIndex]) { 
        totalMatchFound++; 
       } 
      } else { 
       smallestArrayTraversed = true; 
      } 
      indices[array - 1] = currentIndex; 
     } 
     if (totalMatchFound == arrays.length - 1) { 
      result.add(arrays[0][baseIndex]); 
     } 
     baseIndex++; 
    } 

    return result.toArray(new Integer[0]); 
} 

Dưới đây là Unit Tests

@Test 
public void commonElementsInNSortedArrayTest() { 
    int arr[][] = { {1, 5, 10, 20, 40, 80}, 
        {6, 7, 20, 80, 100}, 
        {3, 4, 15, 20, 30, 70, 80, 120} 
        }; 

    Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{20, 80})); 

    arr = new int[][]{ 
      {23, 34, 67, 89, 123, 566, 1000}, 
      {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234}, 
      {23, 43, 67, 98, 566, 678}, 
      {1, 4, 5, 23, 34, 76, 87, 132, 566, 665}, 
      {1, 2, 3, 23, 24, 344, 566} 
      }; 

    result = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{23, 566})); 
}