Найти общие элементы в двух несортированных массивах

Question

Я пытаюсь найти решение этой проблемы: У меня есть два массива A и B целых чисел (A и B могут иметь разные размеры). Я должен найти общие элементы в этих двух массивах. У меня есть другое условие: максимальное расстояние между общими элементами - k. Итак, это мое решение. Я думаю, это правильно:

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 
    } 
} 

Есть ли способ сделать лучшее решение? Какие-либо предложения? Заранее спасибо!

Answer 1

Хотя это было бы чит, так как он использует HashSet s, это довольно хорошо для реализации этого алгоритма Java. Если вам нужен псевдокод для алгоритма, не читайте дальше.

Источник и автор в JavaDoc. Приветствия.

/** 
* @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

Учитывая ваше объяснение, я думаю, самый прямой подход чтения массива А, помещая все элементы в Set (множества А), сделать то же самое с B (SETB), и использовать метод retainAll, чтобы найти пересечение обоих элементов (элементов, принадлежащих обоим наборам).

Вы увидите, что k distance не используется вообще, но я не вижу возможности использовать это условие, которое приводит к коду быстрее или более надежным. Решение, которое я защищаю, работает без соблюдения этого условия, поэтому оно работает также, когда условие истинно (это называется «ослабление предварительных условий»)

Answer 3

IMPLEMENT BINARY SEARCH AND QUICK SORT!

это приведет к тоннам кода .... но самый быстрый результат.

Вы можете сортировать элементы большего массива с помощью быстрого сортировки, что приведет к O (nlogn).

затем перебираем меньший массив для каждого значения и выполняем двоичный поиск этого конкретного элемента в другом массиве. Добавьте некоторую логику для расстояния в двоичном поиске.

Я думаю, вы можете получить сложность до O (nlogn). Худший случай O (n^2)

псевдо-код.

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 

это самый быстрый способ сделать вашу проблему, я верю.

Answer 4

Ваша реализация примерно равна O (A.length * 2k).

Это, кажется, о лучшем случае вы будете делать, если вы хотите сохранить вашу «не более чем к прочь» логике, как исключает сортировку и использование наборов. Я бы немного изменил, чтобы сделать ваш код более понятным.

1. Во-первых, я гарантирую, что вы выполните итерацию по меньшему из двух массивов. Это создало бы сложность O (min (A.length, B.length) * 2k).

   Чтобы понять цель этого, рассмотрим случай, когда A имеет 1 элемент и B имеет 100.В этом случае мы будем выполнять только одну итерацию во внешнем цикле и k итераций во внутреннем цикле.

   Теперь рассмотрим, когда A имеет 100 элементов, а B имеет 1. В этом случае мы проведем 100 итераций по внешнему циклу и по 1 итерации на внутреннем контуре.

   Если k меньше длины вашего длинного массива, то итерация по более короткому массиву во внешнем цикле будет более эффективной.

2. Тогда я бы изменил, как вы вычисляете материал расстояния k только для удобства чтения. Код, который я написал, демонстрирует это.

Вот что я хотел бы сделать:

//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]); 
     } 
    } 
} 

Использование jlimit и ks может работать, но обработка вашего K расстояние, как это более понятно для среднего программиста (и это немного более эффективным) ,

Answer 5

Родовой раствор

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())); 
} 

Выходной

[b] 
[1, 4] 

Answer 6

O раствор (Н) (BloomFilters):

Вот решение с использованием цветения фильтров (реализация от Гуава)

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; 
} 

использовать его как это:

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()); 

Запускается в O (N), поскольку вычисление хеш для Integer довольно прямо вперед. Таким образом, все еще O (N), если вы можете уменьшить вычисление хэша ваших элементов до O (1) или небольшого O (K), где K - размер каждого элемента.

O решение (N.LogN) (сортировка и итерация):

Сортировка и итерация по массиву приведет вас к O (N * Log) (N) решение:

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(~) в O (N) конечно. Arrays.sort(~) представляет собой двунаправленную реализацию QuickSort со сложностью в O (N.logN), а повторение через массив снова - O (N).

Итак, мы имеем O ((N + 2) .logN) ~> O (N.logN).

В общем случае решение (с условием «внутри k» вашей проблемы) лучше, чем ваше. Его следует рассматривать для k «близко к» N в вашем конкретном случае.

Answer 7

Простое решение, если массивы уже отсортированы

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 коллекция API сделала это эффективным способ без сортировки

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

решения с использованием 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()); 
} 

использовать массивы :: asList и значения в штучной упаковке примитивов:

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