Я сталкивался с этой проблемой много раз в различных ситуациях. Он является общим для всех языков программирования, хотя мне нравится C или Java.
Рассмотрим два массива (или коллекции):
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
Как получить общие элементы между двумя массивами как новый массив?
В этом случае пересечение массива A и B будет char[] c = {'c', 'd'}.
Я хочу избежать повторной итерации одного массива внутри другого массива, который будет увеличьте время выполнения на (длина A раз длины B), что слишком велико в случае огромных массивов.
Есть ли способ сделать один проход в каждом массиве, чтобы получить общие элементы?
Так как это выглядит как строковый алгоритм, я на мгновение буду считать, что его невозможно отсортировать (следовательно, строку), тогда вы можете использовать алгоритм Longest Common Sequence (ЛВП)
Предполагая, что размер ввода является постоянным, проблема имеет сложность O (nxm), (длина двух входов)
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). Это происходит не так часто, гораздо реже, чем чистые добавки. Таким образом, сложность времени AMORTIZED равна 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 - 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
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 (для 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))
);
Очевидно, это предполагает, что оба массива не будут иметь дубликатов, и в этом случае использование определенной структуры данных будет иметь больший смысл и более эффективно использовать этот вид операции, особенно если вы не начинаете с массива примитивов с самого начала.
Может или может не соответствовать вашему варианту использования, но вроде как безвкусный подход для общего случая.
Асимптотически это усложняет сортировку. то есть 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)), а элементы должны быть сопоставимы
Сначала сортируйте два массива, используя лучший алгоритм сортировки.
Затем с помощью линейного поиска вы можете получить общие элементы.
Если предоставляется дополнительное пространство, мы можем использовать хеш-таблицу для этого.
в рубине вы можете просто сказать
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 или новее. Пример кода С#:
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 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");
}
}
код >
Если коллекции уже отсортированы, как показано в вопросе, то наилучшим решением (еще не упомянутым) является алгоритм слияния-сортировки, который работает в O (n + m).
Сравните первые элементы каждой коллекции. Если они одинаковы, добавьте элемент в набор пересечений и поместите оба элемента из своих коллекций. Если элементы разные, поместите элемент, который больше, по сравнению с другим элементом. Повторяйте до тех пор, пока не будет опущена одна коллекция.
Используя функции Java 8, вот алгоритм, который отличает дубликаты в списке вместо того, чтобы превращать список в набор. Нет сортировки, поэтому нет n log 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.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]+" ");
}
}
}
}
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]);
}
}
}