这是一个创建于 2129 天前的主题，其中的信息可能已经有所发展或是发生改变。
前言
AI 考拉的技术小哥翻箱底，翻到了以前高三的一道脑洞题，特意拿出来，跟大家一起来挑（怀）战（念）一下题（青）目（春）。
题目是这样的：
有 12 个大小一样的铁球，其中有一颗是劣质品，除了这个劣质品，其他 11 个重量都一样，现在只有一个天平⚖。请问无论遇到什么情况，至少需要称几次才能找到这个劣质品。
从算法的角度去解题， 相当于给了一条这样的题目：给定一个 n 位长度的数组，里面除了一个数字与其他数不一样，其他数字都一样。
如输入 [2, 2, 2, 1], n >= 3
要求：输出 3
如输入 [2, 2, 4, 2], n >= 3
要求：输出 2
且：时间复杂度尽量小。
class Solution {
public int findDifference (int[] nums) {
if (nums[0] !== nums[1]) {
if (nums[0] !== nums[2])
return 0;
else
return 1;
}
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i+1])
return i+1;
}
return -1;
}
}
这个是 $$O(n)$$ 的实现。
这里如何优化算法，就先不讲了，本次还是重点讲题目
一般的常规思路（如下图）就是不断对半平分：
可是第一次对半平分肯定就会出现不平衡的情况，那接下来该如何处理了呢？
1 三等分
1.1 假如第一次遇到的是平衡的状况
第一次就遇到平衡的状况就很好处理了，是最幸运的情况，一下子就将目标锁定在这 4 个上面
接下来随便用橙色 1 号，与 3 号 /4 号 去判断就可以，得出结果了。
所以最好情况下就只要三次的情况下找出来了。
1.2 假如第一次遇到的是不平衡的状况
那接下来该是去称 A 还是称 B 呢？
问题接下来就变成了 如何在 8 个小球内找出一个劣质小球。
看上去 8 个内找出唯一的问题小球还是需要 3 步及以上的。
那有没有办法在两步内找出 8 个小球内的劣质小球呢。
2. 办法肯定是有的：
（极其关键一步）
接下来会遇到两种情况：
2.1 假如第二次平衡了
要留心刚刚蓝球 2，蓝球 3，蓝球 4 这一边的天平一开始是往下还是往上的，
假如是往下的，说明劣质球是偏重的，
假如是往上的，说明劣质球是偏轻的，
第三次 ： 对比蓝球 2，蓝球 3，找出劣质的。 若天平平衡，则劣质球是蓝 4
2.2 假如第二次不平衡了
这个时候要观察红球 2，红球 3，红球 4 的天平， 相对于第二次称时，上下是否反转了
（这个也是关键）
2.2.1 若上下反转了，说明劣质球就在红 1 和蓝 1 之间，但是这个时候你还是不知道到底劣质球是重点的还是轻点的。所以还需要多一次对比。（第三次）
2.2.2 若上下没有反转了，说明红 1 和蓝 1，还有蓝 2，3，4 都是正常的，问题出在红 2，红 3，红 4 上。
此时红 2，红 3，红 4 的天平上下代表了劣质品的轻重。
第三次称下红 2，红 3 就可以找出劣质品了
所以，十二个球，无论遇到什么情况，最少秤出的次数还是 3 次。
若有其他想法，也欢迎小伙伴留言反馈哈。
End
 |
1
felixlong 2019-02-27 14:56:51 +08:00
切。这是我娃小学三年级学而思的套路题。
|
 |
2
GeruzoniAnsasu 2019-02-27 15:16:13 +08:00
完了，在 v 站看到过有个神人的博客，有一篇就是讲这个称球问题和 google 那个摔鸡蛋问题的数学原理的
翻了翻收藏夹居然没有。。。 哪位老哥有印象的跪求重发一次 是一篇讲 什么规划 的方法论的东西 还没咋看懂 |
 |
3
dapang1221 2019-02-27 15:21:31 +08:00
信息熵，每称一次的信息量是 log3，总的信息量是 log24，次数就是 log24/log3，取整是 3 …
|
|
4
dapang1221 2019-02-27 15:22:36 +08:00
算了，洗洗睡吧，多少年的老题目了…
|
 |
5
zjl03505 2019-02-27 15:28:09 +08:00
之前看过二进制法解题
|
 |
6
lc4t 2019-02-28 13:38:26 +08:00 via iPhone
3 次，小学竞赛题见过...好老了吧
|
Select Language