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

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__


    排序太浪费了吧

__BlueGuy__

cokeboL 发表于 2013-04-01 14:24
回复 20# __BlueGuy__

我不知道你的程序速度是多少
排序 + 二分 也就 nlgn

你们都不要再回复我， 我拒绝回复这样的弱智题

cokeboL

回复 23# __BlueGuy__


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

__BlueGuy__

楼主不适合写程序， 鉴定完毕 ！

__BlueGuy__

你们对算法的理解完全停留在幼儿园的水平， 跟你们都没法交流

fender0107401

__BlueGuy__ 发表于 2013-04-01 14:38
楼主不适合写程序， 鉴定完毕 ！

装逼男。

别动不动的就在那里“笑而不语”，我相信众多版友都知道你装逼装到没话说的时候经常整一句“笑而不语”。

__BlueGuy__

fender0107401 发表于 2013-04-01 16:10
装逼男。

别动不动的就在那里“笑而不语”，我相信众多版友都知道你装逼装到没话说的时候经常整一句 ...

排序 + 二分 比你的算法不高明？ 我哪里装了？
查个数连个 二分都想不到， 你写JB个程序啊 ...

你那个破算法，都不知道你是怎么想出来的？傻B

笑而不语 ！

fender0107401

__BlueGuy__ 发表于 2013-04-01 16:26
排序 + 二分 比你的算法不高明？ 我哪里装了？
查个数连个 二分都想不到， 你写JB个程序啊 ...

果然又笑而不语了。。。

用这种方式装逼的还真是少见，基本上算得是硬装逼流了。

注：别以为二分查询很牛逼，二分查询的计算复杂性是O(1)，但是这并不代表你说的那个方法跑的快，以你这种经常“笑而不语”的智商，我相信你肯定能理解。