JavaScript-一道经典的面试题目求解(Javascript称球问题)

JavaScript-一道经典的面试题目求解(Javascript称球问题)

想挽留 发布于 2017-06-27 字数 379 浏览 1153 回复 4

这是之前碰到的一个面试题,一直没有找到理想的解答,希望牛人们不吝赐教。(百度google上的就不用重复贴了)

x是一个数组,下标从1到n,其中只有一个数不同于其它。给你函数compare(a,b) a,b:Array of [1..n],比较x[a[1]]+x[a[2]]+……和x[b[1]]+x[b[2]]+……的结果,返回-1,0或1。现在请编写程序在最少的compare调用次数内找出x中那个独一无二的数的下标。(你只能使用compare,x是私有属性)

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

瑾兮 2017-10-01 4 楼

compare的结果只有3种,而总共可能的情况有2N种。因此最少的步骤k需要满足3^k >= 2N

记:从N个球中,找出轻或重的一个,该问题为F(N);

第一步:
将球分成3份,分别是k、k、N-2k个,然后比较k个和k个。如果相等,剩下的问题就是在N-2k个中间找出不同的,即F(N-2k);
如果不相等,问题转化为:有两堆各k个球,有可能是第一堆中有一个不一样的重球,也有可能第二堆中有一个不一样的轻球;
记:N个球中有一个偏重,或另N个球中有一个偏轻,找出不同的一个,该问题为G(N)。该问题一共有2*N种可能的情况。允许借用额外的球。
则问题转化为G(k)。按照尽量将可能情况等分的原则,k = N - 2k时比较合理。

对G(k)来说,下一步:
从偏重堆、偏轻堆中各取出两堆各m个球(一共4堆),并且将重堆和轻堆取出的分组合并然后比较,即:重堆1 + 轻堆1 compare 重堆2 + 轻堆2
依据比较的结果,可以将问题归为:重堆1、轻堆2;重堆2、轻堆1;剩下的
即G(m),G(m),G(k-2m)三种。不难想象m > n时必然有G(m) >= G(n),因此使max(m, k-2m)最小即可,即大约三等分。

因此g(k) = min_m{max(g(m), g(k-2m)) + 1}
g(k)表示解决G(k)问题需要的最小步数。同时也可以断言,当max(m, k-2m)最小时整个表达式有最小值,即:
g(k) = g(ceil(k/3)) + 1

回到问题F,有
f(N) = min_k{ max(f(N-2k), g(k)} + 1}
同时g(1) = 1,f(1) = 1(需要借用额外的球)
不难用数学归纳法证明:f(k) = g(k)

明白了方法,用代码写出来就不是太难了。

归属感 2017-08-31 3 楼

豆瓣上有个关于这个问题的解法讨论,但是没有给出程序代码,可以看看:

http://www.douban.com/group/topic/2287834/

甜柠檬 2017-08-24 2 楼

对于N=12的情况,可以这样来解:

var get4 = function(a, b, c, d) {
return (compare([a, b], [c, d]) > 0) ? (compare([a], [b]) > 0 ? a : b) : (compare([c], [d]) > 0 ? c : d);
};
var getItem = function() {
switch (compare([1, 2, 3, 4], [5, 6, 7, 8])) {
case 0: get4(9, 10, 11, 12);
case 1: get4(1, 2, 3, 4);
case -1: get4(5, 6, 7, 8);
}
};

其他算法可以参考这里。

偏爱自由 2017-07-11 1 楼

称球问题,岂不是传说中的分少数份然后比较总和,每次分要做一步检测,余下的n是大于2小于10之间几的倍数,是几就分几份,不能分两份,因为那个不同的数不知道是比其他大还是小,然后每份求和,用compare函数,找出不同的那个,这样就找出来了