Ответ 1

Так как это выглядит как строковый алгоритм, я на мгновение буду считать, что его невозможно отсортировать (следовательно, строку), тогда вы можете использовать алгоритм Longest Common Sequence (ЛВП)

Предполагая, что размер ввода является постоянным, проблема имеет сложность O (nxm), (длина двух входов)

Ответ 2

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) в пространстве.

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

Ответ 3

Нижняя граница эффективности равна 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). Это происходит не так часто, гораздо реже, чем чистые добавки. Таким образом, сложность времени AMORTIZED равна O (1). Мы не заботимся о том, чтобы некоторые из добавлений принимали O (n) раз, пока большинство добавок занимает O (1) раз.

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

Ответ 4

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

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 - List.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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

• Сортируйте оба массива.
• Затем выполните цикл, пока они не будут иметь общие элементы. Один из массивов достигнет своего конца.

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

Ответ 9

Если вам нужны дубликаты, используйте хеш-карту для индекса 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 для возврата, поскольку он предоставляет нам способ добавления и итерации через список для нашего неизвестного размера.

Ответ 10

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

Ответ 11

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

Ответ 12

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

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

Ответ 13

в рубине вы можете просто сказать

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

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

Ответ 14

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

Код находится здесь:

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, 

Ответ 15

Предполагая, что вы имеете дело с символами 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 с точки зрения сложности пространства.

Ответ 16

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

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

Ответ 17

Сортировка одного из массивов (m Log (m)) теперь выберите каждый элемент из другого массива и выполнить двоичный поиск в первом массиве (отсортированный) → n Log (m)

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

Ответ 18

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

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

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

//

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

код >

Ответ 19

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

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

Ответ 20

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

• Преобразование одного из списков в карту со значением, являющимся числом вхождений (стоимость: O (n)).
• Для каждого элемента в другом списке, если элемент существует на карте, уменьшите значение на единицу (стоимость: 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].

Ответ 21

импортировать java.util.Scanner;

public class 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]+" ");
        }
    }

}

}

Ответ 22

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

  }
}