Tìm các phần tử phổ biến trong hai mảng không phân loại

Question

Tôi cố gắng tìm một giải pháp cho vấn đề này: Tôi có hai mảng A và B số nguyên (A và B có thể có các thứ nguyên khác nhau). Tôi phải tìm các yếu tố chung trong hai mảng này. Tôi có một điều kiện khác: khoảng cách tối đa giữa các phần tử phổ biến là k. Vì vậy, đây là giải pháp của tôi. Tôi nghĩ là chính xác:

for (int i = 0; i<A.length; i++){ 
    for (int j=jlimit; (j<B.length) && (j <= ks); j++){ 
     if(A[i]==B[j]){ 
      System.out.println(B[j]); 
      jlimit = j; 
      ks = j+k; 
     }//end if 
    } 
} 

Có cách nào để đưa ra giải pháp tốt hơn không? Bất kỳ đề xuất? Cảm ơn trước!

Answer 1

Mặc dù đây sẽ là cheat, vì nó sử dụng HashSet s, nó là khá tốt đẹp cho một thực hiện Java của thuật toán này. Nếu bạn cần mã giả cho thuật toán, đừng đọc thêm nữa.

Nguồn và tác giả trong JavaDoc. Chúc mừng.

/** 
* @author Crunchify.com 
*/ 
public class CrunchifyIntersection { 

    public static void main(String[] args) { 
     Integer[ ] arrayOne = { 1, 4, 5, 2, 7, 3, 9 }; 
     Integer[ ] arrayTwo = { 5, 2, 4, 9, 5 }; 

     Integer[ ] common = iCrunchIntersection.findCommon(arrayOne, arrayTwo); 

     System.out.print("Common Elements Between Two Arrays: ");  
     for(Integer entry : common) { 
       System.out.print(entry + " "); 
     } 
    } 

    public static Integer[ ] findCommon(Integer[ ] arrayOne, Integer[ ] arrayTwo) { 

     Integer[ ] arrayToHash; 
     Integer[ ] arrayToSearch; 

     if(arrayOne.length < arrayTwo.length) { 
      arrayToHash = arrayOne; 
      arrayToSearch = arrayTwo; 
     } else { 
      arrayToHash = arrayTwo; 
      arrayToSearch = arrayOne; 
     } 

     HashSet<Integer> intersection = new HashSet<Integer>(); 

     HashSet<Integer> hashedArray = new HashSet<Integer>(); 
     for(Integer entry : arrayToHash) { 
      hashedArray.add(entry); 
     } 

     for(Integer entry : arrayToSearch) { 
      if(hashedArray.contains(entry)) { 
       intersection.add(entry); 
      } 
     } 

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

Answer 2

Với lời giải thích của bạn, tôi nghĩ rằng cách tiếp cận trực tiếp nhất là đọc mảng A, đặt tất cả các yếu tố trong một Set (Seta), làm tương tự với B (SETB), và sử dụng phương pháp retainAll để tìm giao của cả hai bộ (các mục thuộc về cả hai bộ).

Bạn sẽ thấy rằng k distance không được sử dụng chút nào, nhưng tôi không thấy cách nào để sử dụng điều kiện dẫn đến mã nhanh hơn hoặc dễ bảo trì hơn. Giải pháp tôi ủng hộ công việc mà không thực thi điều kiện đó, vì vậy nó cũng hoạt động khi điều kiện là đúng (được gọi là "làm suy yếu điều kiện tiên quyết")

Answer 3

TÌM KIẾM TÌM KIẾM VÀ NHANH CHÓNG NHANH!

điều này sẽ dẫn đến tấn mã .... nhưng kết quả nhanh nhất.

Bạn có thể sắp xếp các phần tử của mảng lớn hơn với kiểu sắp xếp nhanh như vậy sẽ dẫn đến O (nlogn).

sau đó lặp qua mảng nhỏ hơn cho mỗi giá trị và thực hiện tìm kiếm nhị phân của phần tử cụ thể đó trong mảng khác. Thêm một số logic cho khoảng cách trong tìm kiếm nhị phân.

Tôi nghĩ bạn có thể giảm độ phức tạp xuống O (nlogn). Trường hợp xấu nhất O (n^2)

mã giả.

larger array equals a 
other array equals b 

sort a 

iterate through b 
     binary search b at iterated index 
    // I would throw (last index - index) logic in binary search 
    // to exit out of that even faster by returning "NOT FOUND" as soon as that is hit. 
     if found && (last index - index) is less than or equal 
      store last index 
      print value 

đây là cách nhanh nhất có thể để giải quyết vấn đề của bạn.

Answer 4

Triển khai của bạn xấp xỉ O (A.length * 2k).

Đó có vẻ là khoảng tốt nhất bạn sẽ làm gì nếu bạn muốn duy trì bạn "không quá k đi" logic, vì điều đó cai trị ra phân loại và việc sử dụng các bộ. Tôi sẽ thay đổi một chút để làm cho mã của bạn dễ hiểu hơn.

1. Trước tiên, tôi sẽ đảm bảo rằng bạn lặp qua nhỏ hơn của hai mảng. Điều này sẽ làm cho độ phức tạp O (min (A.length, B.length) * 2k).

   Để hiểu mục đích của điều này, hãy xem xét trường hợp trong đó A có 1 phần tử và B có 100.Trong trường hợp này, chúng ta sẽ chỉ thực hiện một phép lặp trong vòng lặp bên ngoài và các phép lặp k trong vòng lặp bên trong.

   Bây giờ hãy cân nhắc khi A có 100 phần tử và B có 1. Trong trường hợp này, chúng tôi sẽ thực hiện 100 lần lặp trên vòng lặp bên ngoài và 1 lặp lại trên vòng lặp bên trong.

   Nếu k nhỏ hơn độ dài của mảng dài của bạn, việc lặp qua mảng ngắn hơn trong vòng lặp ngoài sẽ hiệu quả hơn.

2. Sau đó, tôi sẽ thay đổi cách bạn tính toán công cụ khoảng cách k chỉ vì mục đích dễ đọc. Mã tôi đã viết thể hiện điều này.

Dưới đây là những gì tôi sẽ làm gì:

//not sure what type of array we're dealing with here, so I'll assume int. 
int[] toIterate; 
int[] toSearch; 

if (A.length > B.length) 
{ 
    toIterate = B; 
    toSearch = A; 
} 
else 
{ 
    toIterate = A; 
    toSearch = B; 
} 

for (int i = 0; i < toIterate.length; i++) 
{ 
    // set j to k away in the negative direction 
    int j = i - k; 

    if (j < 0) 
     j = 0; 

    // only iterate until j is k past i 
    for (; (j < toSearch.length) && (j <= i + k); j++) 
    { 
     if(toIterate[i] == toSearch[j]) 
     { 
      System.out.println(toSearch[j]); 
     } 
    } 
} 

Việc bạn sử dụng jlimit và ks có thể làm việc, nhưng xử lý k khoảng cách của bạn như thế này là dễ hiểu hơn cho lập trình viên trung bình của bạn (và nó nhẹ hiệu quả hơn) .

Answer 5

giải pháp Generic

public static void main(String[] args) { 
    String[] a = { "a", "b" }; 
    String[] b = { "c", "b" }; 
    String[] intersection = intersection(a, b, a[0].getClass()); 
    System.out.println(Arrays.toString(intersection)); 
    Integer[] aa = { 1, 3, 4, 2 }; 
    Integer[] bb = { 1, 19, 4, 5 }; 
    Integer[] intersectionaabb = intersection(aa, bb, aa[0].getClass()); 
    System.out.println(Arrays.toString(intersectionaabb)); 
} 

@SuppressWarnings("unchecked") 
private static <T> T[] intersection(T[] a, T[] b, Class<? extends T> c) { 
    HashSet<T> s = new HashSet<>(Arrays.asList(a)); 
    s.retainAll(Arrays.asList(b)); 
    return s.toArray((T[]) Array.newInstance(c, s.size())); 
} 

Output

[b] 
[1, 4] 

Answer 6

O (N) giải pháp (BloomFilters):

Đây là một giải pháp sử dụng bộ lọc nở (thực hiện là từ Thư viện ổi)

public static <T> T findCommon_BloomFilterImpl(T[] A, T[] B, Funnel<T> funnel) { 
    BloomFilter<T> filter = BloomFilter.create(funnel, A.length + B.length); 
    for (T t : A) { 
     filter.put(t); 
    } 
    for (T t : B) { 
     if (filter.mightContain(t)) { 
      return t; 
     } 
    } 
    return null; 
} 

sử dụng nó như thế này:

Integer j = Masking.findCommon_BloomFilterImpl(new Integer[]{12, 2, 3, 4, 5222, 622, 71, 81, 91, 10}, new Integer[]{11, 100, 15, 18, 79, 10}, Funnels.integerFunnel()); 
    Assert.assertNotNull(j); 
    Assert.assertEquals(10, j.intValue()); 

Chạy trong thời gian O (N) kể từ khi tính toán hash cho Integer là khá thẳng về phía trước. Vì vậy, vẫn O (N) nếu bạn có thể làm giảm tính toán băm của các phần tử của bạn thành O (1) hoặc một O nhỏ (K) trong đó K là kích thước của mỗi phần tử.

O (N.LogN) giải pháp (phân loại và lặp lại):

Sắp xếp và các iterating qua mảng sẽ dẫn bạn đến một O (log N * (N)) giải pháp:

public static <T extends Comparable<T>> T findCommon(T[] A, T[] B, Class<T> clazz) { 
    T[] array = concatArrays(A, B, clazz); 
    Arrays.sort(array); 
    for (int i = 1; i < array.length; i++) { 
     if (array[i - 1].equals(array[i])) {  //put your own equality check here 
      return array[i]; 
     } 
    } 
    return null; 
} 

concatArrays(~) có trong O (N) tất nhiên. Arrays.sort(~) là triển khai bi-pivot của QuickSort với độ phức tạp trong O (N.logN) và lặp lại qua mảng lần nữa là O (N).

Vì vậy, chúng tôi có O ((N + 2) .logN) ~> O (N.logN).

Giải pháp trường hợp chung (với điều kiện "trong k" của vấn đề của bạn) tốt hơn của bạn. Nó nên được xem xét cho k "gần" N trong trường hợp chính xác của bạn.

Answer 7

giải pháp đơn giản nếu mảng đã được sắp xếp

public static void get_common_courses(Integer[] courses1, Integer[] courses2) { 
     // Sort both arrays if input is not sorted 
     //Arrays.sort(courses1); 
     //Arrays.sort(courses2); 
     int i=0, j=0; 
     while(i<courses1.length && j<courses2.length) { 
      if(courses1[i] > courses2[j]) { 
       j++; 
      } else if(courses1[i] < courses2[j]){ 
       i++; 
      } else { 
       System.out.println(courses1[i]); 
       i++;j++; 
      } 
     } 
} 

Apache commons bộ sưu tập API đã làm điều này theo cách hiệu quả mà không cần sắp xếp

public static Collection intersection(final Collection a, final Collection b) { 
    ArrayList list = new ArrayList(); 
    Map mapa = getCardinalityMap(a); 
    Map mapb = getCardinalityMap(b); 
    Set elts = new HashSet(a); 
    elts.addAll(b); 
    Iterator it = elts.iterator(); 
    while(it.hasNext()) { 
     Object obj = it.next(); 
     for(int i=0,m=Math.min(getFreq(obj,mapa),getFreq(obj,mapb));i<m;i++) { 
      list.add(obj); 
     } 
    } 
    return list; 
} 

Answer 8

Giải pháp sử dụng Java 8

static <T> Collection<T> intersection(Collection<T> c1, Collection<T> c2) { 
    if (c1.size() < c2.size()) 
     return intersection(c2, c1); 
    Set<T> c2set = new HashSet<>(c2); 
    return c1.stream().filter(c2set::contains).distinct().collect(Collectors.toSet()); 
} 

Sử dụng Mảng :: asList và giá trị đóng hộp của nguyên thủy:

Integer[] a =...  
Collection<Integer> res = intersection(Arrays.asList(a),Arrays.asList(b));