foreach element e in array A
    insert e into hash table H

foreach element e in array B
    if H contains e 
        print e

этот алгоритм O(N) во время O(N) в пространстве.

чтобы избежать дополнительного пространства, вы можете использовать сортировку подход.

нижняя граница эффективности-O (n) - вам нужно хотя бы прочитать все элементы. Тогда есть несколько аппорачей:

тупой самый простой подход

поиск каждого элемента из массива один в массиве два. Временная сложность O (n^2).

сортировка подхода

вам нужно отсортировать только массив один, а затем искать элементы из массива два с помощью двоичного поиска. Временная сложность: сортировка O (nlogn), поиск O (n * logn) = O (nlogn), всего O (nlogn).

хэш-подход

создать хэш-таблицу из массива один элемент. Поиск элементов формирует вторую таблицу в хэш-таблице. Сложность зависит от хэш-функции. Вы можете достичь O (1) для поиска в оптимальном случае(все элементы будут иметь разное хэш-значение), но O (n) в худшем случае (все элементы будут иметь одинаковое хэш-значение). Общая временная сложность: O (n^x), где x-коэффициент эффективности хэш-функции (от 1 до 2).

некоторые хэш-функции гарантированно создают таблицу без коллизий. Но здание больше не занимает строго O (1) времени для каждого элемента. В большинстве случаев это будет O(1), но если таблица заполнена или происходит столкновение, то таблица должна быть перефразирована - принимая O(n) время. Это происходит не так часто, гораздо реже, чем чистые добавляет. Таким образом, АМОРТИЗИРОВАННАЯ временная сложность равна O(1). Мы не заботимся о некоторых добавлениях, занимающих O(n) время, пока большинство из них добавляет занимает O(1) времени.

но даже в этом случае, в крайнем случае, таблица должна быть перефразирована каждой вставкой, поэтому строгая временная сложность будет O (n^2)

есть несколько методов на некоторых языках, о которых я знаю, которые делают именно то, что вы хотите, вы рассматривали некоторые из этих реализаций?

PHP -array_intersect ()

$array1 = array("a" => "green", "red", "blue");
$array2 = array("b" => "green", "yellow", "red");
$result = array_intersect($array1, $array2);
print_r($result);

>> green
   red

Java -список.retainAll

Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));

listOne.retainAll( listTwo );
System.out.println( listOne );

>> dingo, hafil, iga

    public static void main(String[] args) {
        char[] a = {'a', 'b', 'c', 'd'};
        char[] b = {'c', 'd', 'e', 'f'};
        System.out.println(intersect(a, b));
    }

    private static Set<Character> intersect(char[] a, char[] b) {
        Set<Character> aSet = new HashSet<Character>();
        Set<Character> intersection = new HashSet<Character>();
        for (char c : a) {
            aSet.add(c);
        }
        for (char c : b) {
            if (aSet.contains(c)) {
                intersection.add(c);
            }
        }
        return intersection;
    }

int s[256] // for considering all ascii values, serves as a hash function

for(int i=0;i<256;i++)
s[i]=0;

char a[]={'a','b','c','d'};
char b[]={'c','d','e','f'};

for(int i=0;i<sizeof(a);i++)
{
   s[a[i]]++;
 }

 for(int i=0;i<sizeof(b);i++)//checker function
 {
     if(s[b[i]]>0)
       cout<<b[i]; 
  }


  complexity O(m+n);
  m- length of array a
  n- length of array b

Google Guava

на это уже есть много хороших ответов, но если вы хотите использовать однострочный подход с использованием библиотеки для ленивого кодирования, я бы пошел с Google Guava (для Java) и его Sets.intersection метод.

^{(нет компилятора под рукой, медведь со мной)}

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};

Set<Character> intersection = Sets.intersection(
    Sets.newHashSet<Character>(Chars.asList(a)),
    Sets.newHashSet<Character>(Chars.asList(b))
);

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

может или не может соответствовать вашему варианту использования, но своего рода беспроблемный подход для общего случая.

1. сортировка обоих массивов.
2. затем сделайте цикл, пока они не будут иметь общие элементы или один из массивов не достигнет своего конца.

асимптотически, это принимает сложность сортировки. т. е. O (NlogN), где N-длина более длинного входного массива.

если вы заботитесь о дубликатах, используйте хэш-карту для индексирования списка A, причем ключ является элементом, а значение-числом, сколько раз этот элемент был замечен.

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

далее, повторите через B, и если значение существует, вычесть 1. Если нет, то ставим 1 в значение на таблица для этого элемента.

наконец, повторите карту и для любого элемента, который имеет значение != 0, выведите как разницу.

private static <T> List<T> intersectArrays(List<T> a, List<T> b) {
    Map<T, Long> intersectionCountMap = new HashMap<T, Long>((((Math.max(a.size(), b.size()))*4)/3)+1);
    List<T> returnList = new LinkedList<T>();
    for(T element : a) {
        Long count = intersectionCountMap.get(element);
        if (count != null) {
            intersectionCountMap.put(element, count+1);
        } else {
            intersectionCountMap.put(element, 1L);
        }
    }
    for (T element : b) {
        Long count = intersectionCountMap.get(element);
        if (count != null) {
            intersectionCountMap.put(element, count-1);
        } else {
            intersectionCountMap.put(element, -1L);
        }            
    }
    for(T key : intersectionCountMap.keySet()) {
        Long count = intersectionCountMap.get(key);
        if (count != null && count != 0) {
            for(long i = 0; i < count; i++) {
                returnList.add(key);
            }
        }
    }
    return returnList;
}

это должно работать в O(n), поскольку мы только повторяем списки каждый раз, и карта один раз. Структуры данных, используемые здесь в Java, должны быть эффективными, так как HashMap строится с емкостью, которая может обрабатывать самый большой размер списков.

Я использую LinkedList для возвращения, как это дает нам способ добавление и повторение списка для нашего пересечения неизвестного размера.

лучше всего вообще не начинать с массивов. Массивы являются оптимальными для произвольного доступа к элементам, но не оптимальными для поиска (что и является поиском пересечения). Как вы говорите о пересечение, вы должны рассматривать массивы как наборы. Поэтому используйте более подходящую структуру данных (в Java, a Set). Тогда задача намного эффективнее.

вы можете использовать дерево, но время будет O (N (log n)) и элементы должны быть сопоставимы

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

Если дополнительное пространство, то мы можем использовать хэш-таблицу для этого.

в Ruby вы можете просто сказать

a = ['a', 'b', 'c', 'd']
b = ['c', 'd', 'e', 'f']
c = a & b

c содержит ['c', 'd']

сначала отсортируйте два массива, затем повторите их, если они являются одним и тем же элементом, добавьте в возвращаемый массив.

код здесь:

public static void printArr(int[] arr){
    for (int a:arr){
        System.out.print(a + ", ");
    }
    System.out.println();
}

public static int[] intersectionOf(int[] arr1, int[] arr2){
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    printArr(arr1);
    printArr(arr2);

    int i=0, j=0, k=0;
    int[] arr = new int[Math.min(arr1.length, arr2.length)];

    while( i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            i++;
        } else if(arr1[i] > arr2[j]){
            j++;
        } else {
            arr[k++] = arr1[i++];
            j++;
        }
    }
    return Arrays.copyOf(arr, k);
}

public static void main(String[] args) {
    int[] arr1 = {1, 2, 6};
    int[] arr2 = {10, 2, 5, 1};
    printArr(intersectionOf(arr1,arr2));
}

выходы:

arr1: 1, 2, 6, 
arr2: 1, 2, 5, 10, 
arr: 1, 2, 

предполагая, что вы имеете дело с символами ANSI. Подход должен быть похож на Unicode, просто измените диапазон.

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
int[] charset = new int[256]

for(int i=0; i<A.length; i++) {
  charset[A[i]]++;
}

теперь повторите над B, и вы можете проверить, если соответствующее значение кодировки для символа повторяется больше 0. Вы можете хранить их в списке или любой другой коллекции.

этот подход принимает o (n) временную сложность и постоянное пространство для ваших проверок, не принимая во внимание ваш новый массив / список, используемый для хранения общие моменты.

Это лучше, чем подход HashSet/Hashtable с точки зрения сложности пространства.

вы можете использовать HashSet в .NET 3.5 или более поздней версии. Пример кода c#:

HashSet<int> set1 = new HashSet<int>(new int[]{8, 12, 13, 15});

HashSet<int> set2 = new HashSet<int>(new int[] { 15, 16, 7, 8, 9 });

set1.IntersectWith(set2);

foreach (int i in set1)

   Console.Write(i+ " ");

//выход: 8 15

сортировка одного из массивов (M Log(m) ) теперь выберите каждый элемент из массива и выполните двоичный поиск в первом массиве(отсортированном) - >N Log (m)

Общая Временная Сложность : -(n+m)Log (m).

Я надеюсь, что следующее будет полезно. Это два разных подхода:

• простое пересечение, где вы сравниваете все элементы из одного массива к другому массиву.

• сортировка и поиск на основе подхода, который сортирует один массив и поиск второго элемента массива в первом массиве с использованием двоичного кода поиск.

//

public class IntersectionOfUnsortedArrays {
    public static void main(String[] args) {
        int[] arr1 = { 12, 4, 17 };
        int[] arr2 = { 1, 12, 7, 17 };
        System.out.println("Intersection Using Simple Comparision");
        printArray(simpleIntersection(arr1, arr2));
        System.out.println("Intersection Using Sort and Binary Search");
        printArray(sortingBasedIntersection(arr1, arr2));
    }

    /*
     * Simple intersection based on the comparison without any sorting.
     * Complexity O(n^2)
     */
    public static int[] simpleIntersection(int[] a, int[] b) {
        int minlen = a.length > b.length ? b.length : a.length;
        int c[] = new int[minlen];
        int k=0;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<b.length;j++){
                if(a[i]==b[j]){
                    c[k++]=a[i];
                }
            }
        }
        int arr[] = new int[k];
        // copy the final array to remove unwanted 0's from the array c
        System.arraycopy(c, 0, arr, 0, k);
        return arr;
    }

    /*
     * Sorting and Searching based intersection.
     * Complexity Sorting O(n^2) + Searching O(log n)
     */

    public static int[] sortingBasedIntersection(int[] a, int[] b){
        insertionSort(a);
        int minlen = a.length > b.length ? b.length : a.length;
        int c[] = new int[minlen];
        int k=0;
        for(int i=0;i<b.length;i++){
            int result = binarySearch(a,0,a.length,b[i]);
            if(result > -1){
                c[k++] = a[result];
            }
        }
        int arr[] = new int[k];
        // copy the final array to remove unwanted 0's from the array c
        System.arraycopy(c, 0, arr, 0, k);
        return arr;
    }

    public static void insertionSort(int array[]) {
        for (int i = 1; i < array.length; i++) {
            int j = i;
            int b = array[i];
            while ((j > 0) && (array[j - 1] > b)) {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = b;
        }
    }

    static int binarySearch(int arr[], int low, int high, int num) {
        if (high < low)
            return -1;
        int mid = (low + high) / 2;
        if (num == arr[mid])
            return mid;
        if (num > arr[mid])
            return binarySearch(arr, (mid + 1), high, num);
        else
            return binarySearch(arr, low, (mid - 1), num);
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(" "+value);
        }
        System.out.println("\n");
    }
}

Если коллекции уже отсортированы, как показано в вопросе, то лучшим решением (еще не упомянутым) является алгоритм сортировки слиянием, который работает в O(n+m).

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

используя функции Java 8, вот алгоритм, который соблюдает дубликаты в списке вместо того, чтобы превратить список в набор. Нет сортировки, так что нет n log n.

1. преобразуйте один из списков в карту, при этом значение будет числом вхождений(стоимость: O (n)).
2. для каждого элемента в другом списке, если элемент существует на карте, уменьшите возникновение на один (стоимость: O (n)).

таким образом, общая стоимость составляет O(n). Код:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class Dup {
  public static void main(String[] args) {
    List<Integer> listA = Arrays.asList(3, 1, 4, 1, 9, 5, 9);
    List<Integer> listB = Arrays.asList(2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3);
    findCommons(listA, listB);
  }

  static void findCommons(List<Integer> listA, List<Integer> listB) {
    Map<Integer, Long> mapA = 
        listA.stream().collect(
            Collectors.groupingBy(Integer::intValue, Collectors.counting()));

    List<Integer> commons = new ArrayList<>();
    listB.stream()
        .filter(e -> mapA.get(e) != null)
        .filter(e -> mapA.get(e) > 0)
        .forEach(e -> {
            mapA.put(e, mapA.get(e) - 1);
            commons.add(e);
        });

    System.out.println(commons);
  }
}

выше код выдам такой вывод:[5, 3, 9, 9].

импорт java.утиль.Сканер;

публичный класс arraycommon {

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    // display common element in two diffrent array
    int sizea,sizeb,i=0,j=0,k=0;
    int count=0;
    System.out.println("enter the size array A:"+'\n');
    sizea=sc.nextInt();
    System.out.println("enter the size array B"+'\n');
    sizeb=sc.nextInt();
    int a[]=new int[sizea];
    int b[]=new int[sizeb];
    int c[]=new int[sizea];


    System.out.println("enter the element in array A:"+'\n');
    for (i = 0; i < sizea; i++) {

        a[i]=sc.nextInt();
    }
    System.out.println("enter the element in array B:"+'\n');
    for (i = 0; i < sizeb; i++) {

        b[i]=sc.nextInt();
    }
    System.out.println("the element in array A:"+'\n');
    for (i = 0; i < sizea; i++) {

        System.out.print(a[i]+" ");

    }
    System.out.println('\n');
    System.out.println("the element in array B:"+'\n');
    for (i = 0; i < sizeb; i++) 
    {

        System.out.print(b[i]+" ");
    }

    for (i = 0; i <sizea; i++) 
    {
        for (j = 0; j < sizeb; j++) 
        {
           if(a[i]==b[j])
           {
               count++;
               c[k]=a[i];
               k=k+1;
           }
        }
    }
    System.out.println('\n');
    System.out.println("element common in array is");

    if(count==0)
    {
        System.out.println("sorry no common elements");
    }
    else
    {
        for (i = 0; i <count; i++) 
        {

        System.out.print(c[i]+" ");
        }
    }

}

}

    simply search each element of first array with each element of second array and stored matched result in third array
class Union
{
  public static void main(String[] args) {
  char a[] ={'f','g','d','v','a'};
  char b[] ={'a','b','c','d','e'};
  char temp[] = new char[5];
  int p=0;
  for(int i=0;i<a.length;i++)
  {
    for(int j=0;j<b.length;j++)
    {
      if(a[i]==b[j])     //searches if both array has common element
      {

        temp[p] = a[i];   //if match found store it in a new array
        p++;
      }

    }

  }
  for(int k=0;k<temp.length;k++)
  {
      System.out.println(temp[k]);
  }

  }
}