小开

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 (NlogN) ，其中 N 是较长输入数组的长度。

小开

最好的方法是根本不要从数组开始。数组对于随机访问元素来说是最优的，但对于搜索来说却不是最优的(这就是寻找交集的全部意义)。在讨论 十字路口时，必须将数组视为集合。因此使用更合适的数据结构(在 Java 中是 Set)。这样任务就更有效率了。

小开

可以使用 tree，但是时间是 O (n (logn)) ，元素必须具有可比性

小开

据我所知，有些语言中有一些方法可以完全满足您的需要，您是否考虑过看看其中的一些实现？

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-列表，全部保留

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

小开

最佳答案

因为在我看来这像是一个字符串算法，所以我暂时假设不可能对这个序列(因此是字符串)进行排序，那么您可以使用最长公共序列算法(LCS)

假设输入大小是常数，那么问题的复杂度为 O (nxm)(两个输入的长度)

小开

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

小开

效率的下限是 O (n)-您至少需要读取所有元素。接下来有几种方法:

愚蠢的简单方法

从数组1中搜索数组2中的每个元素。时间复杂度 O (n ^ 2)。

分类方法

您只需要对数组1进行排序，然后使用二进制搜索从数组2中搜索元素。时间复杂度: 排序 O (nlogn) ，搜索 O (n * logn) = O (nlogn) ，总 O (nlogn)。

大麻进场

从数组1元素创建哈希表。在哈希表的第二个表中搜索元素。时间复杂度取决于散列函数。在最佳情况下可以实现搜索 O (1)(所有元素具有不同的哈希值) ，但在最坏情况下可以实现 O (n)(所有元素具有相同的哈希值)。总时间复杂度: O (n ^ x) ，其中 x 是 hash 函数效率的一个因子(介于1和2之间)。

一些哈希函数保证构建一个没有冲突的表。但是建筑物不再需要严格的 O (1)时间为每个元素。在大多数情况下，它将是 O (1) ，但是如果表已满或遇到冲突，则需要重新散列该表——需要 O (n)时间。这种情况并不经常发生，远不如干净添加频繁。所以摊销时间复杂度为 O (1)。我们不关心一些加法花费 O (n)时间，只要大多数加法花费 O (1)时间。

但即便如此，在极端情况下，表的每个插入都必须重新散列，因此严格的时间复杂度为 O (n ^ 2)

小开

谷歌番石榴

对于这个问题已经有很多很好的答案，但是如果您想要使用延迟编码库的一行程序方法，我会选择谷歌番石榴(用于 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))
);

显然，这是假设两个数组都没有重复，在这种情况下，使用集合数据结构将更有意义，并且允许这种类型的操作更有效率，特别是如果您不是从一个原语数组开始的话。

可能适合也可能不适合您的用例，但是对于一般用例来说是一种无需思考的方法。

小开

如果您关心重复项，那么可以使用散列映射来索引列表 A，其中键为元素，值为该元素的出现次数。

您迭代第一个元素以及 A 中的每个元素，如果它不存在于 map 中，则将其放在值为1的位置，如果它已经存在于 map 中，则将其添加到该值中。

接下来，循环访问 B，如果值存在，则减去1。如果不是，将 -1放在表中该元素的值中。

最后，循环遍历 map，对于任何具有值! = 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)中运行，因为我们只迭代每个 List 一次，而 Map 一次。Java 中使用的 Data 结构应该是高效的，因为构造 HashMap的容量可以处理最大的列表。

我使用 LinkedList作为返回值，因为它为我们提供了一种添加和迭代未知大小交集列表的方法。

小开

假设您处理的是 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 方法要好。

小开

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

小开

首先，使用最佳排序算法对两个数组进行排序。
然后，通过线性搜索，您可以得到公共元素。

如果提供了一个额外的空间，那么我们可以使用散列表来做到这一点。

小开

你可以说

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

C 包含[‘ c’，‘ d’]

小开

您可以在.NET 3.5或更高版本中使用 HashSet:

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

//产出: 815

小开

排序一个数组(mLog (m)) 现在从其他数组中选择每个元素在第一个数组(排序的数组)中执行二进制搜索-> n Log (m)

总时间复杂度:-(n + m)对数(m)。

小开

首先对两个数组进行排序，然后迭代它们，如果它们是相同的元素，则添加到要返回的数组中。

密码在这里:

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,

小开

我希望以下内容能有所帮助。这是两种不同的做法:

比较一个数组中所有元素的简单交集到另一个数组
一种基于排序和搜索的方法，对一个阵列进行排序，对第一个阵列中的第二个阵列元素进行二进制搜索搜索

//




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)中的类似合并排序的算法。

比较每个集合的第一个元素。如果它们相同，将元素添加到交集中，并从集合中弹出两个元素。如果元素不同，则弹出比另一个元素大的元素。重复，直到一个集合为空。

小开

使用 Java8特性，这里有一个算法，它可以在列表中保持重复，而不是将列表转换为集合。没有分类，所以没有 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]。

小开

导入 java.util. Scanner;

公共类数组公共值{

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


}
}

我如何得到两个数组之间的交集作为一个新的数组？

愚蠢的简单方法

分类方法

大麻进场

谷歌番石榴