我如何获得两个数组之间的交集作为一个新的数组？
在各种情况下，我多次遇到这个问题。 尽pipe我对C或Java感到满意，但它对所有的编程语言都是通用的。
让我们考虑两个数组（或集合）：
char[] A = {'a', 'b', 'c', 'd'}; char[] B = {'c', 'd', 'e', 'f'}; 我如何获得两个数组之间的公共元素作为一个新的数组？ 在这种情况下，数组A和B的交集是char[] c = {'c', 'd'} 。
我想要避免在另一个数组内重复迭代一个数组，这将会增加执行时间（长度是B的A倍长度），这对于巨大的数组来说太多了。
有没有什么办法可以在每个数组中进行一次传递以获得通用元素？
由于这看起来像一个stringalgorithm，我会假设它不可能sorting这个序列（因此string），那么你可以使用最长序列algorithm（LCS）
假设input大小是恒定的，那么问题的复杂度为O（nxm），（两个input的长度）
foreach element e in array A insert e into hash table H foreach element e in array B if H contains e print e
这个algorithm在时间上是O(N) ，在空间上是O(N) 。
为了避免额外的空间，你可以使用基于sorting的方法。
效率的下限是O（n） – 你至less需要读取所有的元素。 然后有几个apporaches：
哑巴最简单的方法
在数组二中search数组1中的每个元素。 时间复杂度O（n ^ 2）。
sorting方法
你只需要sorting一个数组，然后使用二进制search从数组2中search元素。 时间复杂度：sortingO（nlogn），searchO（n * logn）= O（nlogn），总O（nlogn）。
哈希办法
从数组一个元素创build一个哈希表。 在哈希表中search元素形成第二个表。 时间复杂度取决于散列函数。 您可以在最佳情况下（所有元素将具有不同的散列值）实现O（1），但在最坏的情况下O（n）（所有元素将具有相同的散列值）。 总时间复杂度：O（n ^ x），其中x是散列函数效率的因子（在1和2之间）。
一些哈希函数保证build立一个没有冲突的表。 但是build筑物不再需要严格的O（1）时间。 在大多数情况下，它将是O（1），但是如果表已满或遇到冲突，那么需要重新对表进行O（n）次处理。 这种情况发生得不是很频繁，比干净添加的频率要less得多。 所以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
现在已经有很多很好的答案，但是如果你想要一个使用一个库来实现延迟编码的Sets.intersection方法，我会使用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)) );
显然，这是假设两个数组都不会有重复，在这种情况下，使用set数据结构会更有意义，并且可以更有效地进行这种操作，特别是如果您不从一开始就从一系列基元开始。
可能会或可能不适合您的使用情况，但是对于一般情况来说，这是一种无需考虑的方法。
- 对两个数组进行sorting。
- 然后循环，直到它们具有共同的元素或者其中一个数组到达其末尾。
渐近地说，这需要sorting的复杂性。 即O（NlogN）其中N是较长input数组的长度。
如果您关心重复项，请使用哈希映射对索引列表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)运行，因为我们只是迭代每个列表和一次Map。 在Java中使用的数据结构应该是高效的，因为HashMap是用一个能够处理最大大小的列表的容量来构造的。
我使用LinkedList作为返回，因为它为我们提供了添加和遍历我们未知大小交集的列表的方法。
最好的方法是不要从数组开始。 数组对于元素的随机访问是最优的，但是对于search来说不是最优的（这就是发现交叉点的原因）。 正如你所说的交集 ，你必须把数组当作集合。 所以使用更合适的数据结构（在Java中，一个Set ）。 那么这个任务就更有效率了。
你可以使用树，但是时间是O（n（log n）），元素必须是可比较的
首先，使用最佳sortingalgorithm对两个数组进行sorting。
然后，用线性search，你可以得到共同的元素。
如果提供了额外的空间，那么我们可以使用散列表来做到这一点。
在ruby，你可以说
a = ['a', 'b', 'c', 'd'] b = ['c', 'd', 'e', 'f'] c = a & b
c包含['c'，'d']
首先对两个数组sorting，然后对它们进行迭代，如果它们是相同的元素，则添加到要返回的数组中。
代码在这里：
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，你可以检查被迭代的字符对应的charset值是否大于0.你可以将它们存储在一个列表或任何其他集合中。
这种方法需要O（n）的时间复杂度，并且不会考虑用于保存公共元素的新数组/列表，而是考虑到您的检查的空间不变。
就空间复杂度而言，这比HashSet / Hashtable方法更好。
您可以在.NET 3.5或更高版本中使用HashSet。 示例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））进行sorting从其他数组中选取每个元素，并在第一个数组（sorting的）中进行二进制search – > n Log（m）
总时间复杂度： – （n + m）Log（m） 。
我希望以下将是有用的。 这是两种不同的接近：
-
简单的交叉点，您可以将一个数组中的所有元素与另一个数组进行比较。
-
基于sorting和search的方法，使用二分search对一个数组进行sorting并在第一个数组中search第二个数组元素。
//
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"); } }
如果集合已经被sorting，如问题所示，那么最好的解决scheme（尚未提到）是一个在O（n + m）中运行的合并sortingalgorithm。
比较每个集合的第一个元素。 如果它们相同，则将该元素添加到交集并从集合中popup两个元素。 如果元素不同，则popup比其他元素更大的元素。 重复，直到一个集合是空的。
使用Java 8function，这里是一个algorithm，尊重列表中的重复，而不是将列表变成一个集合。 没有sorting，所以没有n log n 。
- 将其中一个列表转换为一个映射，其值为出现次数（成本：O（n））。
- 对于另一个列表中的每个项目，如果该项目存在于地图中，减less一个（成本：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] 。
import java.util.Scanner;
公共类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]); } } }
