Chinaunix首页 | 论坛 | 博客
  • 博客访问: 340921
  • 博文数量: 54
  • 博客积分: 446
  • 博客等级: 下士
  • 技术积分: 821
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-30 17:37
文章分类

全部博文(54)

文章存档

2015年(35)

2014年(19)

我的朋友

分类: C/C++

2015-09-07 14:19:40

  照例还是每天刷一些笔面试题,今天的两道题是和集合有关的:
 1. A、B两个整数集合,设计一个算法求他们的交集,尽可能的高效。
  这是腾讯一年的笔试题。这里插一句,昨天刚刚考过腾讯的笔试,感觉相对于阿里,腾讯的题更注重对基础的考察,但包罗面比较广,应该来说如果认真将操作系统,数据结构,网络等计算机最基础的知识都准备一下(要拿出考研的热情,根据自己基础准备3~6个月),再大致练一些coding,过腾讯的笔试不应该有很大的问题。
   言归正传,假设集合用数组存储,首先对数组排序,则时间复杂度为O(nlogn),然后基于两个排过序的数组,进行比较求交集,复杂度为O(n),先贴上代码:
          

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define M 8
  4. #define N 5
  5. int cmp(const void *a, const void *b)
  6. {
  7.     int *x = (int *)a;
  8.     int *y = (int *)b;
  9.     return (*x) - (*y);
  10. }

  11. int main(void)
  12. {
  13.     int A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};
  14.     int B[] = {39 ,8 , 10, 6, -1};
  15.     //对数组A和数组B进行快排
  16.     qsort(A, M, sizeof(int), cmp);
  17.     qsort(B, N, sizeof(int), cmp);
  18.     //FindIntersection(A, B);
  19.     int i = 0, j = 0;
  20.     int cnt = 0;
  21.     int result[M > N ? M : N];//保存集合的结果
  22.     //设置i、j索引,分别指向数组A和B,相等则同时移动,不相等则移动较小值的索引
  23.     while(i < M && j < N)
  24.     {
  25.         if(A[i] == B[j])
  26.         {
  27.             result[cnt] = A[i];
  28.             i++;
  29.             j++;
  30.             cnt++;
  31.         }
  32.         else if(A[i] < B[j])
  33.         {
  34.             i++;
  35.         }
  36.         else
  37.         {
  38.             j++;
  39.         }
  40.     }
  41.     for(i = 0; i < cnt; i++)
  42.     {
  43.         printf("%4d", result[i]);
  44.     }
  45.     return 0;
  46. }
代码一目了然,没有什么可说的,需要重点说一下的是qsort函数,qsort函数是编译器自带的快速排序函数,详细介绍如下:
 
头文件:stdlib.h
用 法: void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
参数: 1 待排序数组首地址
            2 数组中待排序元素数量
            3 各元素的占用空间大小
            4 指向函数的指针,用于确定排序的顺序
关于fcmp函数的书写方式,维基百科上有更标准的写法,这里也贴一下,以供参考:
        

点击(此处)折叠或打开

  1. /* Comparison function. Receives two generic (void) pointers. */
  2. int compare(const void *p, const void *q)
  3. {
  4.     int x = *(const int *)p;
  5.     int y = *(const int *)q;
  6.     /* to avoid undefined behaviour through signed integer overflow,
  7.         avoid: return x - y; */
  8.     int ret;
  9.     if (x == y)
  10.       ret = 0;
  11.     else
  12.       ret = (x < y) ? -1 : 1;

  13.     return ret;
  14. }
  2. 已知集合A和B的元素分别用不含头结点的单链表存储,函数difference()用于求解集合A与B的差集,并将结果保存在集合A的单链表中。例如,若集合A={5,10,20,15,25,30},集合B={5,15,35,25},完成计算后A={10,20,30}。
   这是迅雷2014年的校招试题,贴上代码

点击(此处)折叠或打开

  1. struct node
  2. {
  3.     int elem;
  4.     node* next;
  5. };

  6. void difference(node** LA , node* LB)
  7. {
  8.     node *pa , *pb , *pre , *q;
  9.     pre = NULL;
  10.     pa = *LA;

  11.     while(pa)
  12.     {
  13.         pb = LB;
  14.         while(pb && pa->elem != pb->elem )
  15.             pb = pb->next;
  16.         if(pb)
  17.         {
  18.             if(!pre)
  19.                 *LA = pa->next ;
  20.             else
  21.                 pre->next = pa->next;
  22.             q = pa;
  23.             pa = pa->next;
  24.             free(q);
  25.         }
  26.         else
  27.         {
  28.             pre = pa;
  29.             pa = pa->next;
  30.         }
  31.     }
  32. }
代码中的指针pa用于指向集合A的元素;pb指向集合B的元素;临时指针q指向需要被删除的元素;pre用于实现删除时结点的链接,与pa保持所指结点的前后继关系

一般来说,集合有两种存储方式,数组或链表,本题两种存储方式都涉及到了,这两题仅是给出了解法,应该不是最高效的方法,后面再不断地更新完善吧!



参考资料:
         维基百科: />          题1代码:http://blog.csdn.net/jie1991liu/article/details/13168255
         题2代码:http://blog.csdn.net/hackbuteer1/article/details/11482103


  
 
阅读(1503) | 评论(0) | 转发(0) |
0

上一篇:IP分片

下一篇:求二进制数中1的个数

给主人留下些什么吧!~~