Найти дубликат в двух массивах

Question

Мой вопрос был связан с поиском дубликатов в двух массивах.

array1 = [1,2,4,6,9,50,34]; 
array2 = [1,5,4,50,24,78,34]; 

Я знаю, что код для этого является использование двух for петли:

for(int i=0; i<arr1.length; i++){ 
    for(int j=0; j<arr2.length; j++) { 
     if(arr1[i]==arr2[j]) { 
      System.out.println(arr1[i]); 
     } 
    } 
} 

Интервьюер попросил лучшего метода с большим количеством итераций. Могу ли я получить какие-либо предложения по этому поводу?

Answer 1

Я снова сделал тесты. .. набор и карты действительно намного быстрее, чем петли

private static int size = 100000; 

public static void main(String[] args) { 
    int[] array1 = new int[size]; 
    int[] array2 = new int[size]; 

    for (int i = 0; i < size; i++) { 
     array1[i] = i; 
     array2[i] = i + i; 
    } 

    System.out.println("starting set"); 
    startTimer(); 
    compareAgainstSet(array1, array2); 
    long set = stopTimer(); 
    System.out.println("against set: " + set + "ms\n"); 

    System.out.println("starting map"); 
    startTimer(); 
    compareAgainstMap(array1, array2); 
    long map = stopTimer(); 
    System.out.println("against hashmap: " + map + "ms\n"); 

    System.out.println("starting loops with break"); 
    startTimer(); 
    twoLoopsWithBreak(array1, array2); 
    long loopsBreak = stopTimer(); 
    System.out.println("2 loops with break: " + loopsBreak + "ms\n"); 

    System.out.println("starting loops without break"); 
    startTimer(); 
    twoLoopsWithoutBreak(array1, array2); 
    long loops = stopTimer(); 
    System.out.println("2 loops without break: " + loops + "ms\n"); 

} 

private static void twoLoopsWithoutBreak(int[] arr1, int[] arr2) { 
    ArrayList<Integer> doubles = new ArrayList<>(); 
    for (int i : arr1) { 
     for (int j : arr2) { 
      if (i == j) { 
       doubles.add(i); 
      } 
     } 
    } 
} 

private static void twoLoopsWithBreak(int[] arr1, int[] arr2) { 
    ArrayList<Integer> doubles = new ArrayList<>(); 
    for (int i : arr1) { 
     for (int j : arr2) { 
      if (i == j) { 
       doubles.add(i); 
       break; 
      } 
     } 
    } 
} 

private static void compareAgainstSet(int[] arr1, int[] arr2) { 
    ArrayList<Integer> doubles = new ArrayList<>(); 
    Set<Integer> set1 = new HashSet<Integer>(); 
    for (int i : arr1) { 
     set1.add(i); 
    } 
    for (int i : arr2) { 
     if (set1.contains(i)) { 
      doubles.add(i); 
     } 
    } 
} 

private static void compareAgainstMap(int[] arr1, int[] arr2) { 
    ArrayList<Integer> doubles = new ArrayList<>(); 
    HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>(); 
    for (int i : arr1) { 
     hashmap.put(i, 0); 
    } 
    for (int i : arr2) { 
     if (hashmap.containsKey(i)) { 
      doubles.add(i); 
     } 
    } 
} 

private static long startTime; 

private static void startTimer() { 
    startTime = System.currentTimeMillis(); 
} 

private static long stopTimer() { 
    return System.currentTimeMillis() - startTime; 
} 

Answer 2

Код с двумя петлями - O (m * n), где m и n - размеры массива. Вы можете сделать это лучше, если вы поместите содержимое одного массива в контейнер на основе хэша, скажем, HashSet<T>, а затем просмотрите элементы второго массива, проверяя, находятся ли они в хэш-наборе или нет. Это имеет сложность O (m + n), т. Е. Линейное по общему числу элементов в обоих массивах.

Answer 3

Требуется ваше решение O(n^2) время (при условии, что n - это длина большего из двух массивов).

Лучшим решением было бы отсортировать два массива - O(n log(n))
, а затем найти дубликаты в одной итерации по обоим отсортированных массивов - O(n).
Общее время работы будет O(n log(n)).

Answer 4

Почему бы не просто использовать array_intersect?

$a = array(1, 2, 5, 10, 15, 16); 
$b = array(1, 4, 5, 6, 10, 13, 15, 19); 

print_r(array_intersect($a, $b)); 

Упс, я учил это PHP, не JS ...

Тогда: How do I get the intersection between two arrays as a new array?

Answer 5

Как dasblinkenlight уже говорил мне:

public static void main(String[] args) { 
     int[] arr1 = new int[] { 10, 3, 4, 20}; 
     int[] arr2 = new int[] { 10, 20, 30 }; 

     //convert arr1 to java.util.Set 
     Set<Integer> set1 = new HashSet<Integer>(); 
     for (int i : arr1) { 
      set1.add(i); 
     } 
     // print the duplicates 
     for (int i : arr2) { 
      if (set1.contains(i)) { 
       System.out.println(i); // print 10 20 
      } 
     } 
    } 

Answer 6

Если вы не хотите, чтобы два для петель. Затем вы можете использовать хеш-таблицу. Итерируйте первый массив и вставьте в hastable. При повторении второго массива в хеш-таблицу, проверьте наличие ключа, если он есть, то он дублируется иначе.

При таком подходе временная сложность будет уменьшаться до O (kn), где k - константа, которая представляет собой количество массивов, которые у вас есть, но дополнительная сложность пространства будет увеличена.

Answer 7

import java.util.*; 
public class Duplicate { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    int array1[]= {1,2,4,6,9,50,34}; 
    int array2[]= {1,5,4,50,24,78,34}; 

    HashSet<Integer> hashValue=new HashSet<>(); 
    for(int i=0;i<array1.length;i++) { 
     hashValue.add(array1[i]); 
    } 

    for(int j=0;j<array2.length;j++) { 
     if(hashValue.contains(array2[j])) { 
      System.out.println("the duplicate value is "+array2[j]); 
     } 
    } 


} 

}