如何取两个已排序数组的交集?
例:
1,3,5,6,7,9
2,4,6,7,8,9
如何能够最快的取出交集.
有没有什么好的算法.我不想去一个一个的循环比较.
[解决办法]
好像没有直接的方法可以用
[解决办法]
没想出来，帮你顶一下，关注中...
[解决办法]
Apache Jakarta Commons 有 Collections 包，里面有个 CollectionUtil.intersection() 方法，就是取两个集合中的交集。
但是对于你的这个问题，看样子好像需要自己设计算法。
[解决办法]
一个一个的循环比较就行了，因为已经排好序了的，如果比较数> =待比较数，就break到下一轮查找，这应该已经很高效了吧……
[解决办法]
必须要遍历。至于算法，也许有比较好的，不过偶不知道。。。。
[解决办法]
因为是排好序了，可以同时搜索
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
Set s = new HashSet();
for (int i=0, j=0; i <a.length && j <b.length; ) {
if (a[i]==b[j]) {
s.add( " "+a[i]);
i++;
j++;
} else if (a[i] > b[j]){
j++;
} else {
i++;
}
}
if (s.size()==0) {
Sytem.out.println( "no intersection ");
} else {
System.out.println(Arrays.toString(s.toArrays()));
}
[解决办法]
collect接口有两个方法你去看下对你很有帮助,就是取交集用的
boolean retainAll(Collection <?> c)
仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。换句话说，移除此 collection 中未包含在指定 collection 中的所有元素。
boolean removeAll(Collection <?> c)
移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。此调用返回后，collection 中将不包含任何与指定 collection 相同的元素。
[解决办法]
如果还不了解.请看下面示例
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
List list = new ArrayList(Arrays.asList(a));
list.retainAll(Arrays.asList(b)); // list 中的就是交集了.
[解决办法]
public static <T> List <T> asList(T... a)
返回一个受指定数组支持的固定大小的列表。（对返回列表的更改会“直接写”到数组。）此方法同 Collection.toArray() 一起，充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。返回的列表是可序列化的，并且实现了 RandomAccess。
[解决办法]
用retainAll当然是最简单的代码，但是这样就体现不出排序数组的优势，
用qybao(阿宝) 的方法可减少循环次数
[解决办法]
如果是未排好序的，Collection可能会快， 但是排好序的Collection就不一定见得比自己写的算法快了。如果追求代码简洁，也可以用Collection
[解决办法]
楼上的和我一样有同感，幸会幸会
[解决办法]
同意阿宝的处理方式。
[解决办法]
你们没看清楚LZ的问题吗??
如何能够最快的取出交集.
有没有什么好的算法.我不想去一个一个的循环比较.
[解决办法]
mark
[解决办法]
在这问题上我同意bushuang的处理方式。
[解决办法]
恩，有新意啊
[解决办法]
1,3,5,6,7,9
2,4,6,7,8,9
用两个整型,第一位代表0,第二位1,以此类推.
如果上面两组数对应整数应该是:
0101011101........
0010101111........
将这两数进行&操作不就得到交集了.
如果整数集合太大就自己做位域吧.
[解决办法]
list.retainAll高
[解决办法]
有个想法可以减少循环，因为是排好序的，所以判断如果b的一个值大于a的一个，那就不用再循环判断b后面的值是不是符合要求的，后面的值一定也大于a，例子如下：
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
ArrayList list = new ArrayList();
for(int i = 0;i < a.length;i++){
//因为是排好序的，判断当a中一个值大于b中一个值的时候就跳出不用再循环b后面的了
for(int j = 0;j < b.length;j++){
if(a[i] = j[i]){
list.add(a[i]);
}elseif(a[i] < j[i]){
return;//如果a[i] <j[i]就跳出
}else{
j++;//如果a[i]> j[i]，就j++继续循环j
}
}
i++;//然后继续循环a
}
这个虽然也循环，但是可以减少循环次数。
[解决办法]
可以用set吗？要是可以拿就简单了．
[解决办法]
public class t{
private int[] a={0,1,3,3,5,7,9};//去比较
private int[] b={-1,0,2,3,4,5,9,9,10};//被比较
private int[] c=null;
public t(){
c=jiaoJi(a,b);
print(); //打印
}
public int[] jiaoJi(int[] a,int[] b){ //处理交集函数
//确定 中间变量数组 jj 的数组大小，其大小为，a,b两数组较小的数组大小
int size;
if (a.length> b.length){
size=b.length;
}else{
size=a.length;
}
//建立中间变量数组 jj
int [] jj=new int [size];
for (int i=0;i <size;i++){ //赋值
jj[i]=0;
}
int k=0;//记录交集元素插入到jj数组的位置
int e=0;//记录 下一次比较的开始位置
for (int i=0;i <a.length;i++){
for (int j=e;j <b.length;j++){
if (a[i]==b[j]){
jj[k++]=a[i]; //存储交集元素，数组jj 下标 k 加一
e=j+1; //记录 下一次比较的开始位置,既从j后面的元素开始
break;//跳出for循环
}
}
}
int [] zzjj=new int[k]; //根据K建立交集的是数组zzjj
for (int i=0;i <k;i++){
zzjj[i]=jj[i];
}
return zzjj;
}
public void print(){//打印
for(int i=0;i <c.length;i++){
System.out.print(c[i]+ ", ");
}
System.out.println();
}
public static void main(String args[]){
new t();
}
}
我这个也行的，测试通过
[解决办法]
楼主的贴子到处贴啊？C++论坛里也贴这个。已经讨论过了，不可能不用循环比较。只不过是看你怎么优化循环了。
[解决办法]
//C++版本
template <class Type>
void union_intersect(vector <Type> & l,vector <Type> & r,vector <Type> & out)
{
sort(l.begin(),l.end());
sort(r.begin(),r.end());
out.clear();
vector <Type> ::iterator IL=l.begin();
vector <Type> ::iterator IR=r.begin();
while(IL!=l.end()&&IR!=r.end())
{
if(*IL <*IR)
{
while(IL!=l.end()&&*IL <*IR)
++IL;
}
else if(*IR <*IL)
{
while(IR!=r.end()&&*IR <*IL)
++IR;
}
else
{
out.push_back(*IL);
++IL; ++IR;
}
}
}
[解决办法]
往hashtable里面插入啊，遇到存在的就是交集的一个数据项
[解决办法]
都写的这么复杂干吗，java里提供了Set类，直接就可以算交集。
------解决方案--------------------
楼主的问题本身就是矛盾的,所以...
[解决办法]
晕，不过是个线性复杂度的问题，至于闹这么大嘛
[解决办法]
btw,为什么不用循环，循环是最基本的控制结构之一，有什么不好？lz怎么不说不用判断……
[解决办法]
因为是排好序了，可以同时搜索
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
Set s = new HashSet();
for (int i=0, j=0; i <a.length && j <b.length; ) {
if (a[i]==b[j]) {
s.add( " "+a[i]);
i++;
j++;
} else if (a[i] > b[j]){
j++;
} else {
i++;
}
}
if (s.size()==0) {
Sytem.out.println( "no intersection ");
} else {
System.out.println(Arrays.toString(s.toArrays()));
}
[解决办法]
排序过了,为什么不用二分查找?
[解决办法]
查找范围是:
两个数组中最大的下限和最小的上限,先判断下这个再做循环二分查找.
[解决办法]
list.retainAll 好像效率不是最高的
用归并， m+n的复杂度
list1 size m
list2 size n
[解决办法]
在串中有个算法佳模式匹配~~
这个可以看作一个特殊的模式匹配算法~~
效率绝对高~~
[解决办法]
//用模式匹配的算法~
public static void getPattern(Object[] strA, Object[] strB) {
// 只要有一个null，就返回null
if (strA == null || strB == null || strA.length == 0
|| strB.length == 0) {
System.out.println( " ");
return;
}
int lengthA = strA.length;
int lengthB = strB.length;
Object[] longStr = lengthA > lengthB ? strA : strB;
Object[] shortStr = lengthA > lengthB ? strB : strA;
Map <Integer, List <Object[]> > maxSubstrList = new TreeMap <Integer, List <Object[]> > ();
for (int length = shortStr.length; length > = 0; length--) {
for (int startIndex = 0; startIndex <= shortStr.length - length; startIndex++) {
Object[] tmpO = new Object[length];
System.arraycopy(shortStr, startIndex, tmpO, 0, length);
String _tmp1 = Arrays.toString(longStr).replaceAll( "\\[ ", " ").replaceAll( "\\] ", " ");
String _tmp2 = Arrays.toString(tmpO).replaceAll( "\\[ ", " ").replaceAll( "\\] ", " ");
if ((_tmp1.indexOf(_tmp2) > -1) && (Arrays.asList(longStr).containsAll(Arrays.asList(tmpO)))) {
int len = tmpO.length;
List <Object[]> list;
if (maxSubstrList.containsKey(len)) {
list = (List <Object[]> ) maxSubstrList.get(len);
} else {
list = new ArrayList <Object[]> ();
}
if (!list.contains(tmpO)) {
list.add(tmpO);
}
maxSubstrList.put(len, list);
}
}
}
//找到所有匹配子串
if (maxSubstrList.size() == 0) {
return;
} else {
Iterator <Entry <Integer, List <Object[]> > > it = maxSubstrList
.entrySet().iterator();
Entry <Integer, List <Object[]> > entry = it.next();
while (it.hasNext()) {
entry = it.next();
List <Object[]> maxList = entry.getValue();
for (Object[] str : maxList) {
System.out.println(Arrays.toString(str));
}
}
}
}
测试：getPattern(new Integer[]{1,2,4,6,7,8,9},new Integer[]{1,3,4,7,8,9,11,22});
结果：
[1]
[4]
[7]
[8]
[9]
[7, 8]
[8, 9]
[7, 8, 9]
[解决办法]
执行循环次数：36次
[解决办法]
遍历一个小的数组，因为有序，复杂度能够做到O(min(n,m))