求两无序不重复数组的交集

//输入：a[]={5,7,8,9,1,2,3 }; b[]={2, 8,10,4,6,7};

//输出：{2,7,8}

[思路1]：

判断a数组元素值的元素是否在b中，是则输出之。

时间复杂度：O（n2）

[cpp]
void cmpInterSection(int a[], int b[], int m, int n)
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0;j < n; j++)
        {
            if(a[i] == b[j])
            {
                cout << a[i] << "\t";
                break;
            }
        }//end for j
    }//end for i
    cout << endl;
}

[思路2]：

1）对两数组进行排序；

2）一次循环判断a和b中元素是否相等，相等则输出；不等则小的值++。

时间复杂度：O（nlogn）

//快排之分割
[cpp]
int divided(int nArr[], int nLeft, int nRight)
{
    int pivot = nArr[nLeft];

    while(nLeft < nRight) //×¢ÒâwhileÑ»•
    {
        while(nLeft < nRight && nArr[nRight] >= pivot) //×¢ÒâµÈºÅ
        {
            --nRight;
        }
        nArr[nLeft] = nArr[nRight];
        while(nLeft < nRight && nArr[nLeft] <= pivot)   //×¢ÒâµÈºÅ
        {
            ++nLeft;
        }
        nArr[nRight] = nArr[nLeft];
    }

    nArr[nLeft] = pivot;
    return nLeft;
}

//快排之递归
void quickCurve(int nArr[], int nLeft, int nRight)
{
    int nPivotPos = 0;
    if(nLeft < nRight)
    {
        nPivotPos = divided(nArr,nLeft,nRight);
        quickCurve(nArr,nLeft,nPivotPos-1);
        quickCurve(nArr,nPivotPos+1,nRight);
    }
}
//快排
void quickSort(int nArr[], int nLen)
{
    quickCurve(nArr,0,nLen-1);
}
void interSectionOfArray(int a[], int b[], int m, int n)
{
    //快排
    quickSort(a,m);
    quickSort(b,n);

    //一次循环筛选出交集.
    if( m < n)
    {
        int j = 0;
        int i = 0;
        while(i < m)
        {
            if(a[i] == b[j])
            {
                cout << a[i] << "\t";
                i++;

                j++;
            }
            else if(a[i] > b[j])
            {
                j++;        //小值++
            }
            else
            {
                i++;        //小值++
            }
        }
        cout << endl;
    }//end if
}

[思路3]：
hash表存储两数组到一个表中，统计次数累计为2的元素输出即可。

时间复杂度：O（n），典型的以空间换时间的方法。

[cpp]
ypedef struct HASHSET
{
    int key; //值
    int nCnt; //计数
}hashSet;

    hashSet* pSetArray = new hashSet[m*n]; //空间换时间
    for(int i = 0; i <m*n; i++)
    {
        pSetArray[i].key = 0;
        pSetArray[i].nCnt = -1;
    }

//O(n)实现输出…
void hashInterSection(hashSet* pSetArray, int a[], int b[], int m, int n)
{
    for(int i = 0; i < m; i++)
    {
        pSetArray[a[i]].key = a[i];
        pSetArray[a[i]].nCnt++;
    }
    for(int j = 0; j < n; j++)
    {
        pSetArray[b[j]].key = b[j];
        pSetArray[b[j]].nCnt++;
    }

    for(int k = 0; k < m*n; k++)
    {
        if(pSetArray[k].nCnt == 1)
        {
            cout << pSetArray[k].key << "\t"; //两次累加-1+1+1=1.
        }
    }
    cout << endl;
}
       或者大家有

补充：软件开发 , C++ ,