口试百度遇到的3道算法题求解

面试百度遇到的3道算法题求解
第一题：
某个公司举行一场羽毛球赛，有1001个人参加，现在为了评比出“最厉害的那个人”，进行淘汰赛，请问至少需要进行多少次比赛。

第二题
有100个灯泡，第一轮把所有灯泡都开启，第二轮把奇数位的灯泡灭掉，第三轮每隔两个灯泡，灭一个，开一个，依此类推。求100轮后还亮的灯泡。

第三题
有20个数组，每个数组里面有500个数组，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。
[解决办法]
第二题如果第n轮就是每个n的灯泡，开的关关的开

#include <stdio.h>

#define PRINT{for (i = 0; i < 100; i++)printf("%d ", ar[i]);printf("\n\n");}
// 0   关着的
// 非0 开着的
int main(void)
{
int ar[100] = {0};
int i;
int times;
int n;
int t;
printf("n = ?: ");
scanf("%d", &n);
for (i = 0; i < 100; i++)
ar[i] = 1;
for (t = 1; t < (n % 100); t++)
{
for (i = 0; i < 100; i += (t + 1))
ar[i] = !ar[i];
PRINT
}
for (i = 0, times = 0; i < 100; i++)
if (ar[i] != 0)
times++;
printf("%d", times);
return 0;
}

[解决办法]
第一题你们想多了，1001个人的淘汰赛自然是最少要举行1000场比赛，问题并不是如何做到这一点。
[解决办法]
1. 1000
2. 灯泡从 1 开始编号，所有编号为完全平方数(1,4,9,...,100)的灯泡最后会亮着。ps.这个是经典题了。
3. 昨天刚好看到类似的题目。以下 n=10000,m=500，有三个方法。
   [1] sort. O(nlogn)
   [2] 将第一数组建立 min-heap，所有其他数组成员依次插入到 min-heap，每次完成插入后，删除当前最小值，即根元素。所有元素都筛过以后，min-heap 中的元素即为最大的 500 个。O(nlogm).
   [3] 将 20 个数组合并为 1 个，挨着连接起来即可，不必保证有序。在合并的数组中随机选取一个元素，然后将所有小于此元素的元素放在其左侧，大于到右侧。完成操作后，如果原来被选中的元素刚好处在右数第 500 的位置，那从它开始向右的元素即为所求。否则，如果右端元素数目大于 500，则对右端序列递归使用此方法；否则，如果左端序列数目大于 10000-500，则对左端序列递归使用此方法。复杂度 expected O(n). 
   [2] 和 [3] 都没有用到原数组有序的特性，我想应该还能改进。
[解决办法]

引用:

1. 1000
2. 灯泡从 1 开始编号，所有编号为完全平方数(1,4,9,...,100)的灯泡最后会亮着。ps.这个是经典题了。
3. 昨天刚好看到类似的题目。以下 n=10000,m=500，有三个方法。
   [1] sort. O(nlogn)
   [2] 将第一数组建立 min-heap，所有其他数组成员依次插入到 min-heap，每次完成插入后……

heap的正宗做法不是nlogk的么，k=20。
[解决办法]

引用:

引用:引用:……
heap的正宗做法不是nlogk的么，k=20。 
为啥?堆中元素个数始终是 500 (m个)，平衡二叉树实现的话，高度是 logm，除第一个数组，其他所有数组的元素都要经过堆的筛选，不是 O(nlogm) 吗。
20个数组的最小元素全部进堆。每次取一个最小的时候，从最小元素对……

后来又想了一下你说的方法，还是有不解之处，能把具体步骤详细发上来吗？把最大堆还是最小堆说清楚，我主要不理解怎么寻找下一个应该出堆的元素以及何时停止算法。就按楼主的要求，20 个数组，每个 500 且已经降序排列，找所有数字中最大的 500 个。
[解决办法]

引用:

引用:引用:引用:……
heap的正宗做法不是nlogk的么，k=20。 
为啥?堆中元素个数始终是 500 (m个)，平衡二叉树实现的话，高度是 logm，除第一个数组，其他所有数组的元素都要经过堆的筛选，不是 O(nlogm) 吗。
20个数组的最小元……

for(int i=0;i<20;i++)
{
  index[i] = 0;
  heap.insert(a[i][index[i]++]); 
 
}
vector<int> result;
while(result.size() < 500)
{
  t = heap.extract_min();
  i = GetIndex(t); // so that the number t comes from array a[i]. pseudo-code writes easy but might need non-trivial amount of work to implement this
  if(index[i] < a[i].size())
    heap.insert(a[i][index[i]++]);
  result.push_back(t);
}

[解决办法]

引用:

第一第二题不用扯算法，直接用逻辑分析就行了。
1：既然是淘汰赛，1场肯定淘汰一个人，1001人最后剩1个冠军，要淘汰1000个人就是1000场
2：一个灯如果被开关奇数次，是灭的；如果被开关偶数次，是亮的。按照这个思路，某个灯在哪一次会被开关呢？答案是当n+1是这个灯号码的约数的时候。比如12的约数有1,2,3,4,6,12那么第12盏灯就在第1,2,3,5,11轮开……

说的非常有道理

第三题
方法如下
1.建立最大堆，依次将20个数组的首个元素入堆，当然堆的节点要记录是属于哪个数组的。
2.弹出堆顶元素，将属于同个数组的后续元素入堆
3.转2
复杂度O(nlogk)   n=500 k=20

查看更多 下一篇