发帖
雷达卡
1、请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在
中所处的位置和变化。队伍可能随时有人加入和退出，当有人退出影响到用户的位置排名时需要即时反馈到用户。
2、A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效。
（本人能力有限，不是所有题目都会求解，第
1题不是我的擅长，这里贴出来让大家知道腾讯的考题。我的重点放在第
2题上面！！）
第2题题解思路1：排序法
对集合A和集合B进行排序（升序，用快排，平均复杂度
O(N*logN)
），设置两个指针
p和q，同时指向集合
A和集合B的最小值，不相等的话移动
*p和*q中较小值的指针，相等的话同时移动指针
p和q，并且记下相等的数字，为交集的元素之一，依次操作，直到其中一个集合没有元素可比较为止。
优点：操作简单，容易实现。
缺点：使用的排序算法不当，会耗费大量的时间，比如对排好序的集合使用快排，
时间复杂度是
O(N2)
这种算法是大家都能比较快速想到的办法，绝大多数时间放在了对集合的排序上，快排的平均复杂度是
O(N*logN)
，对排好序的集合做查找操作，时间复杂度为
O（N），当然这种算法肯定比遍历要快多了。
c ...
京公网安备 11010802022788号
