有什么算法可以很快地取到交集。

cokeboL

比如都是int数组
计数：
分配个大数组清零，每个int数组元素作为大数组下标对大数组元素做++，各个数组都弄完之后，遍历一次大数组看哪些元素值和数组个数相等，取其下标为交集

如果是字符串之类的并且字符串数量不是特别大，弄个字符串和int的映射表，一样可以用上面的方法
数量巨大弄映射伤不起的话，楼主描述下数据特点吧，然后再想牛逼的算法吧。。。

cokeboL

如果遍历的话，各数组长度分别是 N_MIN， N_1， N_2 。。。 N_MAX

1.先N_MIN和N_1中找，N_MIN中每个元素和N_1中比较看是否有相等的，复杂度为O(N_MIN * N_1)
2.结果再和N_2比较，1中交集个数<= N_MIN，这里复杂度为O(N_MIN * N_2)
。。。
总复杂度为O(N_MIN * （N_1 + N_2 + ... N_MAX))也很大

我去搜搜

cokeboL

回复 9# selfrun


    树本身的操作带来的额外复杂度可能已经太大了

cokeboL

回复 10# shan_ghost


    我感觉排序没必要，直接遍历比较应该更省

cokeboL

回复 14# selfrun


我是说，map或树本身的操作，就一堆代码，同样的O(n)，用树和for(  i < n  )相比，实际操作数上树、map要多很多

而且你看看遍历比较的，复杂度也没多高

cokeboL

回复 16# selfrun


空间复杂度没多大的，用C++的话也可以vector之类的，如果事先就找出各个数组中长度最小的n_min，空间复杂度最大也不会超过n_min，而且还可以不超过

第一个找出的交集长度，时间却会省很多

cokeboL

1. #include <stdio.h>
   
2. 
   
3. #define NON_EXIST (-1)
   
4. #define ARR_SIZE_MAP(arr_n) { arr_n, sizeof(arr_n)/sizeof(arr_n[0]) }
   
5. 
   
6. int n_1[] = {1, 2, 3, 5, 8, 9, 14};
   
7. int n_2[] = {2, 3, 6, 7, 10, 14};
   
8. //...
   
9. int n_max[] = {1, 3, 14, 15, 28};
   
10. 
    
11. static int *arr_mixed = 0;
    
12. 
    
13. static struct Arr_map{
    
14.     int *array_n;
    
15.     int array_size;
    
16. }array_size_map[] = {
    
17.     ARR_SIZE_MAP(n_1),
    
18.     ARR_SIZE_MAP(n_2),
    
19. //    ...
    
20.     ARR_SIZE_MAP(n_max)
    
21. };
    
22. 
    
23. void arr_mixed_init(struct Arr_map *am)
    
24. {
    
25.     if(arr_mixed){
    
26.         free(arr_mixed);
    
27.         arr_mixed = 0;
    
28.     }
    
29.    
    
30.     arr_mixed = (int*)malloc(am->array_size + 1);
    
31.     if(!arr_mixed){
    
32.         printf("arr_mixed malloc failed: %m");
    
33.         return;
    
34.     }
    
35.         for(int i = 0; i < am->array_size; i++){
    
36.                 arr_mixed[i] = am->array_n[i];
    
37.     }
    
38.     arr_mixed[am->array_size] = NON_EXIST;
    
39. }
    
40. 
    
41. void arr_mixed_destroy()
    
42. {
    
43.         if(arr_mixed){
    
44.             free(arr_mixed);
    
45.         arr_mixed = 0;
    
46.         }
    
47. }
    
48. 
    
49. //function for test print
    
50. void print_arr_map(struct Arr_map am[], int am_len)
    
51. {
    
52.         for(int i = 0; i < am_len; i++){
    
53.                 printf("am[%d] size %d: ", i, am[i].array_size);
    
54.                 for(int j = 0; j < am[i].array_size; j++){
    
55.                         printf("%2d ", am[i].array_n[j]);
    
56.                 }
    
57.                 printf("\n");
    
58.         }
    
59. }
    
60. 
    
61. void find_mixed(struct Arr_map am[], int am_len)
    
62. {
    
63.         print_arr_map(am, am_len);
    
64.     arr_mixed_init(&am[0]);
    
65. 
    
66.     for(int i = 1; i < am_len; i++){
    
67.         int count = 0;     
    
68.         for(int j = 0; arr_mixed[j] != NON_EXIST; j++){
    
69.             for(int k = 0; k < am[i].array_size; k++){
    
70.                 if(arr_mixed[j] == am[i].array_n[k]){
    
71.                     arr_mixed[count++] = arr_mixed[j];
    
72.                                         break;
    
73.                 }
    
74.                                
    
75.             }        
    
76.         }
    
77.         arr_mixed[count] = NON_EXIST;
    
78.     }
    
79. }
    
80. 
    
81. int main()
    
82. {
    
83.     find_mixed(array_size_map, sizeof(array_size_map)/sizeof(array_size_map[0]));
    
84.         printf("\nmixed foud: ------------>\n");
    
85.         for(int i = 0; arr_mixed[i] != NON_EXIST; i++){
    
86.         printf("arr_mixed[%d]: %d\n", i, arr_mixed[i]);
    
87.     }
    
88.     arr_mixed_destroy();
    
89. }

复制代码

cokeboL

回复 20# __BlueGuy__


    排序太浪费了吧

cokeboL

回复 23# __BlueGuy__


    那你写一个排序+二分的然后比较下速度试试

cokeboL

求楼主贴用各种算法的代码和实际测试结果