White's Studio.

找出不合格品

脑洞题
2018/09/28 Share

找出不合格品

最近找出来草稿纸，看到一条高三时做的有趣的脑洞题。

题目是这样的：

有12个大小一样的铁球，其中有一颗是劣质品，除了这个劣质品，其他11个重量都一样，现在只有一个天平⚖。请问无论遇到什么情况，至少需要称几次才能找到这个劣质品。

题目忘了是谁提出来的，当时整个班的同学都开始想怎样解题。

从算法的角度去解题， 相当于给了一条这样的题目：给定一个 n 位长度的数组，里面除了一个数字与其他数不一样，其他数字都一样。

如输入 [2, 2, 2, 1], n >= 3

要求：输出 3

如输入 [2, 2, 4, 2], n >= 3

要求：输出 2

且：时间复杂度尽量小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.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~

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/09/28/找不出合格品/

发表日期: September 28th 2018, 11:07:42

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 找出不合格品
    1. 1.1. 1 三等分
      1. 1.1.1. 1.1 假如第一次遇到的是平衡的状况
      2. 1.1.2. 1.2 假如第一次遇到的是不平衡的状况
    2. 1.2. 2. 办法肯定是有的：
      1. 1.2.1. 2.1 假如第二次平衡了
      2. 1.2.2. 2.2 假如第二次不平衡了
        1. 1.2.2.1. 2.2.1 若上下反转了，说明劣质球就在红1和蓝1之间，但是这个时候你还是不知道到底劣质球是重点的还是轻点的。所以还需要多一次对比。（第三次）
        2. 1.2.2.2. 2.2.2 若上下没有反转了，说明红1和蓝1，还有蓝2，3，4都是正常的，问题出在红2，红3，红4上。
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm