照例还是每天刷一些笔面试题,今天的两道题是和集合有关的:
1.
A、B两个整数集合,设计一个算法求他们的交集,尽可能的高效。
这是腾讯一年的笔试题。这里插一句,昨天刚刚考过腾讯的笔试,感觉相对于阿里,腾讯的题更注重对基础的考察,但包罗面比较广,应该来说如果认真将操作系统,数据结构,网络等计算机最基础的知识都准备一下(要拿出考研的热情,根据自己基础准备3~6个月),再大致练一些coding,过腾讯的笔试不应该有很大的问题。
言归正传,假设集合用数组存储,首先对数组排序,则时间复杂度为O(nlogn),然后基于两个排过序的数组,进行比较求交集,复杂度为O(n),先贴上代码:
-
#include <stdio.h>
-
#include <stdlib.h>
-
#define M 8
-
#define N 5
-
int cmp(const void *a, const void *b)
-
{
-
int *x = (int *)a;
-
int *y = (int *)b;
-
return (*x) - (*y);
-
}
-
-
int main(void)
-
{
-
int A[] = {-1, 2 ,39 ,10, 6, 11, 188, 10};
-
int B[] = {39 ,8 , 10, 6, -1};
-
//对数组A和数组B进行快排
-
qsort(A, M, sizeof(int), cmp);
-
qsort(B, N, sizeof(int), cmp);
-
//FindIntersection(A, B);
-
int i = 0, j = 0;
-
int cnt = 0;
-
int result[M > N ? M : N];//保存集合的结果
-
//设置i、j索引,分别指向数组A和B,相等则同时移动,不相等则移动较小值的索引
-
while(i < M && j < N)
-
{
-
if(A[i] == B[j])
-
{
-
result[cnt] = A[i];
-
i++;
-
j++;
-
cnt++;
-
}
-
else if(A[i] < B[j])
-
{
-
i++;
-
}
-
else
-
{
-
j++;
-
}
-
}
-
for(i = 0; i < cnt; i++)
-
{
-
printf("%4d", result[i]);
-
}
-
return 0;
-
}
代码一目了然,没有什么可说的,需要重点说一下的是qsort函数,qsort函数是编译器自带的快速排序函数,详细介绍如下:
头文件:stdlib.h
用 法: void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
2 数组中待排序元素数量
3 各元素的占用空间大小
关于fcmp函数的书写方式,维基百科上有更标准的写法,这里也贴一下,以供参考:
-
/* Comparison function. Receives two generic (void) pointers. */
-
int compare(const void *p, const void *q)
-
{
-
int x = *(const int *)p;
-
int y = *(const int *)q;
-
/* to avoid undefined behaviour through signed integer overflow,
-
avoid: return x - y; */
-
int ret;
-
if (x == y)
-
ret = 0;
-
else
-
ret = (x < y) ? -1 : 1;
-
-
return ret;
-
}
2.
已知集合A和B的元素分别用不含头结点的单链表存储,函数difference()用于求解集合A与B的差集,并将结果保存在集合A的单链表中。例如,若集合A={5,10,20,15,25,30},集合B={5,15,35,25},完成计算后A={10,20,30}。
这是迅雷2014年的校招试题,贴上代码
-
struct node
-
{
-
int elem;
-
node* next;
-
};
-
-
void difference(node** LA , node* LB)
-
{
-
node *pa , *pb , *pre , *q;
-
pre = NULL;
-
pa = *LA;
-
-
while(pa)
-
{
-
pb = LB;
-
while(pb && pa->elem != pb->elem )
-
pb = pb->next;
-
if(pb)
-
{
-
if(!pre)
-
*LA = pa->next ;
-
else
-
pre->next = pa->next;
-
q = pa;
-
pa = pa->next;
-
free(q);
-
}
-
else
-
{
-
pre = pa;
-
pa = pa->next;
-
}
-
}
-
}
代码中的指针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) |