问题: 给你两个排序的数组,求两个数组的交集。
比如: A = 1 3 4 5 7, B = 2 3 5 8 9, 那么交集就是 3 5.
思路:
1. 每一次从B数组中取一值,然后在A数组里逐个比较,如果有相等的,则保存。该算法复杂度为 O(MN). M, N 分别为数组 A B 的长度。
2. 因为A B 都排过序,所以,每一次从B数组取值后,可以利用二分查找看是否在数组A里有B所对应的值,这样复杂度变成了O(N lg M)。 这里,如果N 比 M 大,可以从A中取值,然后在B中判断是否有A的值,这样,复杂度为 O(M lg N)。
3. 利用hashtable. 先把A中的值存在hashtable里,然后对于每一个B中的值,判断是否在A中存在,因为hashtable查找的平均复杂度为 O(1), 所以,整个算法复杂度为O(N), 但是,这里的空间复杂度为 O(M) 。但是,这种方法适合数组比较小的情况。因为如果A数组比较大,hashtable会出现collision的情况,这样,查找的平均复杂度就不再是O(1)。
本文方法:
因为数组A B均排过序,所以,我们可以用两个“指针”分别指向两个数组的头部,如果其中一个比另一个小,移动小的那个数组的指针;如果相等,那么那个值是在交集里,保存该值,这时,同时移动两个数组的指针。一直这样操作下去,直到有一个指针已经超过数组范围。
public LinkedList<Integer> intersection(int[] A, int[] B) {
if (A == null || B == null || A.length == 0 || B.length == 0) return null;
LinkedList<Integer> list = new LinkedList<Integer>();
int pointerA = 0;
int pointerB = 0;
while (pointerA < A.length && pointerB < B.length) {
if (A[pointerA] < B[pointerB]) pointerA++;
else if (A[pointerA] > B[pointerB]) pointerB++;
else {
list.add(A[pointerA]);
pointerA++;
pointerB++;
}
}
return list;
}
通过上面的算法可以得知,该算法复杂度为O(N + M).
扩展:
给两个排序的数组,求两个数组的并集。
转载请注明出处:http://blog.csdn.net/beiyeqingteng
分享到:
相关推荐
数组求交集.c
c语言基础 c语言基础_c语言编程基础之数组操作示例_两个数组的交集
查找数组中的重复元素,且时间复杂度为O(n)
利用指针来实现动态数组,求两个集合的交集和并集。(要求用动态数组来实现)依次分别输入数组A、B长度,并输入A,B中元素,即可得到交集并集
本文实例讲述了Python实现求两个数组交集的方法。分享给大家供大家参考,具体如下: 一、题目 给定两个数组,编写一个函数来计算它们的交集。 例1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 例2: ...
// res得到两个数组中交集 [2,2,3,4] var res = arr1.filter(function (item, index) { // 那arr1中的数据 去arr2数组中检测在arr2是否存在 // arr2.indexOf(item) 检测arr2中否是有 item这个数据 // 有数据就...
两个数组的交集给定两个数组,编写一个函数来计算它们的交集。示例 1:输出:[2]示例 2:输出:[9,4]def intersection(self, nums
绝对不吃亏!绝对不吃亏!绝对不吃亏! 元素的操作方法1.el是否包含某个class 字符串的操作方法1.去除空格2....判断类型集合1.手机号码2....数字转换1....判断一个元素是否在数组中2.去重 并集 交集 最大值 最小值
从数组1的尚未比较的元素中拿出第一个元素array1(i),用array1(i)与array2(j)进行比较(其中j>i且j的长度),可能出现下面两种情况, 1. 数组2中找到了一个与array1(i)相等的元素,则将array2(j)与array2(i)进行...
Java 实例 - 计算两个数组交集源代码-详细教程.zip
数组求交集(C语言),入门小程序,适合C语言入门的小练习 数组求交集(C语言),入门小程序,适合C语言入门的小练习 数组求交集(C语言),入门小程序,适合C语言入门的小练习 数组求交集(C语言),入门小程序...
示例 1:输出:[2,2]示例 2:输出:[4,9]vector<int> intersect(vector<int>& nums1, vector<int>&
自己编写的程序,实现两个有序数组求交集。例如a={1,2,3,4,5,6,7},b={1,3,5,8,9,11},则结果为{1,3,5}
本文实例讲述了JavaScript获取两个数组交集的方法。分享给大家供大家参考。具体如下: 这里传入的数组必须是已经排过序的 /* finds the intersection of * two arrays in a simple fashion. * * PARAMS * a - ...
&数组与,返回两数组的交集 [1,2] & [2,3] =>[2] *复制数组n次 [1,2]*2 => [1,2,1,2] +返回两数组的并集,但不排除重复元素 [1,2]+[2,3] =>[1,2,2,3] 追加元素,但不排除重复元素 [1,2][2,3] => [1,2,2,3] 等
本文通过多种实现方式给大家介绍了JS计算两个数组的交集、差集、并集、补集 的相关知识,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
C#Linq获取两个List或数组的差集交集.pdf
js代码-(算法)两个数组交集