Tìm phần tử tối đa phổ biến trong hai mảng?

Question

Với hai mảng, cách tìm phần tử tối đa chung cho cả hai mảng là gì?

Tôi đã suy nghĩ về sắp xếp cả mảng (n log n) và sau đó thực hiện tìm kiếm nhị phân của mọi phần tử từ một mảng được sắp xếp (bắt đầu từ mảng lớn hơn) trong mảng khác cho đến khi kết hợp được tìm thấy.

ví dụ:

a = [1,2,5,4,3] 
b = [9,8,3] 

Maximum common element in these array is 3 

Chúng ta có thể làm tốt hơn so với n log n?

Answer 1

Với một số không gian thừa, bạn có thể băm trong 1 mảng, sau đó thực hiện chứa trên mỗi phần tử của mảng khác theo dõi giá trị lớn nhất trả về giá trị đúng. Sẽ là O (n).

Answer 2

Bạn có thể sử dụng không gian O(N).
Chỉ cần đi qua mảng đầu tiên và đặt tất cả các phần tử trong một số HashTable. Đây là O(N)
Sau đó, đi qua bản theo dõi mảng thứ hai của mức tối đa hiện tại và kiểm tra xem phần tử có nằm trong số HashTable hay không. Đây cũng là O(N). Vì vậy, tổng thời gian chạy là O(N) và O(N) thêm không gian cho Ví dụ HashTable

trong Java:

public static int getMaxCommon(int[] a, int[] b){ 
    Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a)); 
    int currentMax = Integer.MIN_VALUE; 
    for(Integer n:b){ 
    if(firstArray.contains(n)){ 
     if(currentMax < n){ 
       currentMax = n 
     } 
    } 
    } 
    return currentMax; 
} 

Answer 3

Trong khi nó phụ thuộc vào sự phức tạp thời gian của các hoạt động khác nhau trong ngôn ngữ cụ thể, làm thế nào về việc tạo ra bộ từ các mảng và tìm giá trị tối đa trong giao điểm của hai bộ? Đi theo thời gian phức tạp cho hoạt động trong Python, nó sẽ được, trung bình, O (n) cho các bài tập thiết lập, O (n) cho giao lộ, và O (n) cho việc tìm kiếm giá trị tối đa. Vì vậy, trường hợp trung bình sẽ là O (n).

Tuy nhiên! Trường hợp xấu nhất sẽ là O (len (a) * len (b)) -> O (n^2), vì sự phức tạp thời gian tồi tệ nhất của các giao điểm được thiết lập. Thông tin

More đây, nếu bạn quan tâm: http://wiki.python.org/moin/TimeComplexity

Answer 4

Nếu bạn đã biết một loạt các con số đó sẽ là trong mảng của bạn, bạn có thể thực hiện đếm sắp xếp, và sau đó thực hiện tìm kiếm nhị phân như bạn muốn. Điều này sẽ mang lại thời gian chạy O (n).

Answer 5

Mã giả:

sort list1 in descending order 
sort list2 in descending order 
item *p1 = list1 
item *p2 = list2 
while ((*p1 != *p2) && (haven't hit the end of either list)) 
    if (*p1 > *p2) 
    ++p1; 
    else 
    ++p2; 
// here, either we have *p1 == *p2, or we hit the end of one of the lists 
if (*p1 == *p2) 
    return *p1; 
return NOT_FOUND; 

Answer 6

Không phải là một hoàn hảo, nhưng một giải pháp đơn giản, O (len (array1) + len (array2))

import sys 


def find_max_in_common(array1, array2): 
    array1 = set(array1) 
    array2 = set(array2) 

    item_lookup = {} 

    for item in array1: 
     item_lookup[item] = True 

    max_item = -sys.maxsize 

    intersection = False 

    for item in array2: 
     if not item_lookup.get(item, None): 
      continue 
     else: 
      intersection = True 
      if item > max_item: 
       max_item = item 

    return None if not intersection else max_item