设计算法，求AB两个整数集合的交集

2023-01-18 10:49:12

【本文链接】

http://www.cnblogs.com/hellogiser/p/ab-set-intersection.html

【分析】

思路1：排序法

　　对集合A和集合B进行排序（升序，用快排，平均复杂度O(N*logN)），设置两个指针p和q，同时指向集合A和集合B的最小值，不相等的话移动*p和*q中较小值的指针，相等的话同时移动指针p和q，并且记下相等的数字，为交集的元素之一，依次操作，直到其中一个集合没有元素可比较为止。

　　优点：操作简单，容易实现。

　　缺点：使用的排序算法不当，会耗费大量的时间，比如对排好序的集合使用快排，时间复杂度是O(N²)

　　这种算法是大家都能比较快速想到的办法，绝大多数时间放在了对集合的排序上，快排的平均复杂度是O(N*logN)，对排好序的集合做查找操作，时间复杂度为O（N），当然这种算法肯定比遍历要快多了。

【代码】

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/10/8
*/

#include "stdafx.h"
#include <iostream>
using namespace std;

int cmp(const void *a, const void *b)
{
    int *x = (int *)a;
    int *y = (int *)b;
    return (*x) - (*y);
}

void intersection(int *A, int M, int *B, int N)
{
    // quick sort
    qsort(A, M, sizeof(int), cmp);
    qsort(B, N, sizeof(int), cmp);
    ;
    ;
    int *result = new int[M > N ? M : N];// save result
    while(i < M && j < N)
    {
        if(A[i] == B[j])
        {
            result[cnt++] = A[i];
            i++;
            j++;
        }
        else if(A[i] < B[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }

//output result
; i < cnt; i++)
    {
        printf("%4d", result[i]);
    }

delete []result;
}

void test_case()
{
    };
    int len1 = sizeof(A) / sizeof(int);
    };
    int len2 = sizeof(B) / sizeof(int);
    intersection(A, len1, B, len2);
}

int main()
{
test_case();
;
}

思路2：索引法

(本质是Bitset方法，要求集合所有数据在【0，range】之内)

以空间换时间，把集合中的元素作为数组下表的索引。来看例子：

A= {1 ,12, 13, 25}，那Asub[1] = 1,Asub[12] = 1 ,Asub[13] = 1 ,Asub[25] = 1 ;

B=｛1, 2, 3, 15 ,｝那Bsub[1] = 1; Bsub[2] = 1; Bsub[3] = 1; Bsub[15] = 1;

　　对元素少的集合扫一遍，发现Asub[1] = 3 和Bsub[1] = 1有相同的索引1，并且重复度为1，所以交集肯定包括{1, 1}; Bsub[2] = 1而Asub[2] = 0，表示无交集，依次类推，可以得到集合A和B的交集。

　　假设集合中存在负数，可以把集合分成正整数和负整数（加个负号变正整数）两部分，解法同上！

　　优点：速度快，时间复杂度O(N)

　　缺点：空间消耗大，以空间换取时间

【扩展】

　　给定两个整数集合A和B，每个集合都包含20亿个不同整数，请给出快速计算A∩B的算法，算法可使用外存，但是要求占用内存不能超过4GB。

　　将集合A的整数，根据n%10不同，分别装入10个文件中，依次命名为a0,a1……,a9。同理，将集合B分别装入10个文件中，依次命名为b0,b1,……,b9。那么A和B编号不同的文件中，一定不会有相同的整数。只需分另求出a0与b0*有的元素、a1与b1*有的元素……。
　　利用bitmap，将bitmap清0，读入文件ai，依次处理每个数，即将bitmap的第（n/10）位置1。然后读入文件bi，依次处理每个数，即：若bitmap第（n/10）位为1，则这个数属于A∩B。

http://www.cnblogs.com/sooner/p/3280050.html

【参考】

http://blog.csdn.net/jie1991liu/article/details/13168255

码农公寓

相关文章