一道C面试题
有16匹马,共3个跑道,找出其中跑的最快的4匹马出来,设计算法。
没听懂什么意思.
我的思路:
从16匹马中,先任选3匹比赛,淘汰最慢的二匹,再从剩下的14匹马中任选3匹比赛,递归,得出最快的前4匹。
时间复杂度,应该是O NlogN
可以用败者树或者堆做吧
就是16个数中取最小的4个数一个道理
如果这个16换成1亿,这个题目看起来就有意思多了
....
所有马都跑一遍
计时
1 给每匹马建立一个集合,集合中包含比这匹马快的马,初始时,所有集合都是空集
2 如果剩下的马是4匹,结束
3 删除所有集合元素个数>=4的马
4 找集合元素个数最小的3匹马出来比赛(元素个数相同的可以任选)
5 根据比赛结果,调整所有集合
6 从2开始继续做
这个方法算不上好,不过还算简单,实现起来也方便
设一个数组arr[3]分别表示3条跑道,每次找两匹马上来跑,跑的最快的存入arr[0]中,再找两匹马来跑,这两匹马中跑的快的和arr[0]中的马比较,跑的快的放在arr[0]中,如此遍历16匹马,arr[0]中的就是最快的马,然后再在剩下的15匹马中用同样的方法找出最快的,......直到找出最快的4匹马
相关问答:
在查询后将查询出来的值赋给各输入框
<c:if test="${not empty dataValue}">
fm.SAMPLING_DATE.value=" <c:out value='${dataValue.SAMPLING_DATE}'/ ......
#include <string.h>
#include <stdio.h>
void main()
{
int i;
char buf[]="abcde";
strncpy(buf,"abc",3);
for(i=0;i <5;i++)
printf(&q ......
13个人围成一圈,从第一个人开始顺序报号1,2,3。凡报到3者退出圈子,找出最后留在圈子中的人原来的序号
结果应该是13 可我的程序的结果是11 希望好心人帮改一下
#include <stdio.h>
#include < ......
如题,求教各位大侠!!多谢
自己顶上~~
longlong
long long
呃~~如果遇到long long都没办法的时候呢?
而且有long long这样的类型?我只记得有long double呵
用数组存,或者自己整个数据结构。
......
写了个简单的hello.c程序,但编译后生成的是obj文件,建工程的时候选 的是win32 动态链接库工程已经。
hello.obj
jni.pch
vc60.idb
vc60.pdb
这些是生成的文件。
hello.c
C/C++ co ......