首页 > 试题广场 >

程序设计：给定2个大小分别为n, m的整数集合，分别存放在两

[问答题]

程序设计：给定2个大小分别为n, m的整数集合，分别存放在两个数组中 int A[n], B[m]，输出两个集合的交集。

查看答案及解析

推荐

Mr_sqw

Java code：

public static int[] intersection(int[] a,int[] b){

int aLen = a.length;

int bLen = b.length;

int aIndex = 0;

int bIndex = 0;

int cIndex = 0;

int[] c = new int[aLen];

Arrays.sort(a);

Arrays.sort(b);

while(aIndex != aLen && bIndex != bLen){

if(a[aIndex] == b[bIndex]){

c[cIndex++] = a[aIndex];

aIndex++;

bIndex++;

}else if(a[aIndex ] < b[bIndex]){

aIndex++;

}else{

bIndex++;

}

if(cIndex != aLen){

c = Arrays.copyOf(c ,cIndex);

}

return c;

}

编辑于 2015-01-28 11:14:56 回复(4)

江小鱼2015

推荐答案是什么鬼。。。时间复杂度明显不是最优的嘛：

两次排序时间复杂度就是 O(mlogm+nlogn)了。。。

个人觉得这道题的正解无非两种：

（1）如果可以hash的话：时间复杂度O(n) 空间复杂度O(m)（n,m可以互换，看你更侧重那个了）

（2）不允许hash（例如取值范围很大）：将短的数组排序，然后二分查找之

时间复杂度是(m+n)log(min(m, n))

编辑于 2016-08-14 19:59:46 回复(1)

文清铄

<？php
$ A = [1,3,4,5,8,9,10];
$ B = [1,2,3,4,5,6,7];
$ jiaoji = [1,2];
$ n_count =计数（array_unique（$ A））;
$ m_count =计数（array_unique（$ B））;
foreach（$ n_count as $ n）{
foreach（$ m_count as $ m）{
if（$ n == $ m）{
$ jiaoji [] = $ n;
}
}
}
var_dump（$ jiaoji）;
？>

发表于 2018-04-03 19:38:37 回复(0)

go_changing

import java.util.Arrays.*
public class PrintAB
{
int A[],int B[];
public void printAB(A,B)
{
    if(A.length<1 ||B.length<1)
         return 0;
int i,j;
     Arrays.sort(A);
     Arrays.sort(B);
     while(i<A.length&&j<B.length)
    {
        if(A[i]<=B[j]
            System.out.print(A[i++]+" ");
        else  System.out.print(B[j++]+" "); }
    if(i==A.length)
    while(i<A.length)  System.out.print(A[i++]+"  ");

  if(i==B.length)  while(i<B.length)   System.out.print(B[j++]+" " );  }
}

发表于 2016-10-11 14:36:02 回复(0)

StrongYoung

有两种思路：1. 直接循环遍历和判断，时间复杂度为n*m；2. 采用空间换时间的思想，空间复杂度为n+m，时间复杂度n+m。

发表于 2015-07-21 13:25:33 回复(0)

MonchiDluffy

#include <iostream>

#include <vector>

using namepsace std;

int main()

{

int n;

int m;

cin >> n >> m;

vector<int> A(n);

vector<int> B(m);

for(int i = 0; i < n; i++)

{

cin >> A[i];

}

for(int i = 0; i < m; i++)

{

cin >> B[i];

}

vector<int> result;

for(int i = 0; i < n; i++)

{

for(int j = 0; j < m; j++)

{

if(A[i] == B[j])

{

result.push_back(A[i]);

}

for(int i = 0; i < result.size(); i++)

{

if(i == 0)

{

cout << result[i];

}

else

{

cout << " " << result[i];

}

return 0;

}

发表于 2017-08-10 21:49:13 回复(0)

biteChris

Python写法 思路就是两个数组排序，然后用两个下标分别指向两个数组，比较大小，
相同则存储，小的则下标加一，直到一个数组遍历完毕结束，算法结束。  def printarray(array1, array2):
    len1 = len(array1)
    len2 = len(array2)
    array1.sort()
    array2.sort()
    i = 0    j = 0    array = []  while i != len1 - 1 or j != len2 - 1:  if array1[i] == array2[j]:
              array.append(array1[i])
              i += 1  j += 1   elif array1[i] < array2[j]:
                i += 1   else:
                j += 1   print array

编辑于 2016-09-05 12:49:51 回复(0)

andy.zhu1

import java.util.Collections;
import java.util.List;

/**
 * 给定2个大小分别为n, m的整数集合，分别存放在两个数组中 int A[n], B[m]，输出两个集合的交集。
 */
public class Question1Answer {

    public static void main(String[] args) {

        int[] a = {5,68,44,33,100,66};
        int [] b = {68,33,2,40,100};

        StringBuffer sb = new StringBuffer();

        for(int i=0;i<a.length;i++){
           for(int j=0;j<b.length;j++){
               if(  a[i] == b[j] ){
                   sb.append(a[i]).append(",");
                   break;
               }
           }
        }

        System.out.print("a,b二个集合的交集是:");
        System.out.println("["+sb.substring(0,sb.length()-1)+"]");
    }
}

发表于 2020-04-02 13:57:10 回复(0)

金山💰

#include<iostream>

#include<vector>

using namespace std;

int main()

{

return 0;
}

发表于 2020-02-26 11:41:08 回复(0)

我真的很菜啊

#include<stdio.h>
int pan_duan(int a[n],int b[m]);
int main(void)
{
int A[n],B[m];

return 0;
}

int pan_duan(int a[n],int b[m])
{
if(m==0||n==0)
return Null;

}

发表于 2019-07-23 20:18:42 回复(0)

牛客657672899号

m= { 1, 2, 4, 5, 7, 8, 9, 11 }

n= { 1, 3, 4, 5, 6 }

k=0

for e in m:

k=k|e

for e in n:

if e==(k&e):

print 'got it',e

发表于 2019-07-05 16:47:12 回复(0)

Disconnect

import java.util*;
public class Main{
    public ArrayList<Integer> findsame(int[] A,int[] B){
         int n = A.length;
         int m = B.length;
         boolean[] boo = new boolean[m]; 
         ArrayList<Integer> al = new ArrayList<Integer>();
       for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++){
                if(A[i]==B[j] && !boo[j]){
                    boo[j] = true;
                    al.add(A[i]);
                    break;
                }    
            }
        }
        return al;
    }
}

发表于 2019-06-07 12:21:04 回复(0)

曹猩猩

发表于 2019-01-25 15:49:22 回复(0)

wisdomshun

return set(A) & set(B)

发表于 2018-11-06 13:47:21 回复(0)

把无味春风融进街边的早餐

int* merge(int A[],int B[])
{
       int * out,m_pA,m_pB;
        m_pA = A;
       m_pB = B;
        int i = 0;
        while(m_pA)
       {
            while(m_pB)
            {
                if(*m_pB==*m_pA)
                {
                    out[i]=*m_pA;
                     i++; 
                }
                m_pB++;
            }
            m_pA++;
        }
         return out;
}

发表于 2018-08-29 09:21:35 回复(0)

skikda

class solution {
public:     vector<int> f(int *a, int *b, int n, int m) {         vector<int>temp, q;         for (int i = 0; i < n; i++) {             temp.push_back(a[i]);         }         for (int i = 0; i < m; i++) {             vector<int>::iterator t = find(temp.begin(), temp.end(), b[i]);             if (t != temp.end()) q.push_back(b[i]);         }         return q;     }
};

发表于 2018-04-14 04:58:26 回复(0)

UNKILLABLEMONSTER

package com.citi.test;

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Vector;

public class Test1 {

    /**
     * 题目描述
     * 程序设计：给定2个大小分别为n, m的整数集合
     * 分别存放在两个数组中 int A[n], B[m]
     * 输出两个集合的交集。
     *
     */

    public static void main(String[] args) {

        int n = 5, m = 3;
        Test1 t = new Test1();
        int[] arr1 = t.inputCollection(n);
        int[] arr2 = t.inputCollection(m);

        Vector<Integer> v = t.getCross(arr1, arr2);

        if(v.size()>0){

            System.out.println("两数组的交集为：");
            for(int o : v)
            {
                System.out.print(o+"    ");
            }

        }
        else

            System.out.println("两数组没有交集！");

    }

    public Vector<Integer> getCross(int[] n, int[] m)
    {
        Vector<Integer> v = new Vector<Integer>();

        for(int i = 0 ; i < n.length ; i ++)
        {

            for(int j = 0 ; j < m.length ; j ++)
            {
                if(n[i] == m[j]&&!v.contains(n[i]))
                    v.addElement(n[i]);
            }
        }

        return v;
    }



    public int[] inputCollection(int n){

        int[] arr = new int[n];

        int i = 0;

        while(i < n){

            i++;

            try {
                Scanner sc = new Scanner(System.in);
                System.out.print("intput number:"+i);
                int a = sc.nextInt();
                arr[i-1] = a;
            } catch (InputMismatchException e) {
                System.out.println("input error, please try again!");
                i--;
            }

        }

        return arr;

    }


}

发表于 2018-03-15 10:53:58 回复(1)

小qaq

将两个数组存放在Set里面，每次存放判断Set的size，size不变的就是重复元素呗。

发表于 2017-08-30 20:34:30 回复(0)

lllagg

感觉只排序一个短的数组，然后让另一个数组来短的数组里找会不会好一些？

发表于 2017-05-27 08:58:09 回复(0)

loving谭

import java.util.ArrayList;  /**  * Created by Administrator on 2017/3/4.  */ public class test1 { public static void main(String[] args) { int[] A = {1,2,3,6,3,6,1,2,7,9,0,54};  int[] B = {1,2,3,7,3,2,7,3,6,1,2,7,9,0,54};  ArrayList<Integer> result = cross(A,B);  System.out.println(result.toString());  } public static ArrayList<Integer> cross(int[] A, int[] B){ ArrayList<Integer> C=new ArrayList<>();  ArrayList<Integer> arrayList=new ArrayList<>();  for (int a : A) {
            arrayList.add(a);  } for (int b:B){ if (arrayList.contains(b)){
                arrayList.remove(arrayList.indexOf(b));  C.add(b);  }
        } return C;  }
}

发表于 2017-03-06 14:47:42 回复(0)

周思源

#include<iostream>
using namespace std;
int main(){
    int n,m,i,j,min,max,A[n],B[m];
    if(n>m){
    min=m;
    max=n;
}else{
min=n;
max=m;
}
    for(i=0;i<min;i++){
        for(j=0;j<max;j++){
            if(A[i]==B[j]){
                    cout<<A[i];
}
}
}
return 0;
}

发表于 2017-02-13 21:58:44 回复(0)

提交观点

问题信息

谷歌数组复杂度

来自：Google2011笔试卷

上传者：冷雨夜

难度：

38条回答 43收藏 19948浏览

程序设计：给定2个大小分别为n, m的整数集合，分别存放在两

问题信息

热门推荐

相关试题