20颗苹果至少要秤几次才能找出最重的那一颗，是遍历19次吗？

昨天在炉石传说掌游宝看到这个问题：：
水果摊上有20颗苹果，重量各有些微差距，但都卖一个2元.
水果摊上还有一个天平秤，如果你想要买到最重的那颗苹果，请问，至少要秤几次才能找出最重的那一颗呢？

标准答案是“不过因为苹果每颗重量都不同，没有更简便的方法，必须每秤一次淘汰一颗比较轻的苹果，所以总共要秤19次，淘汰掉19颗苹果才能找到最重的那一颗”，不过评论区有称3次的，也有称4次的，评论如下：

这是真的吗？到底要怎么秤，为什么

这就相当于冒泡排序第一轮，必须要19次比较才能把最大的排到第一位找出来，那些说3次4次的都没仔细看题，他们都是按20个苹果，只有一个重量不一致来解的，而现在的题是20个苹果每个都不一样，且只有细微差别，可以简化一下，加入同样条件，只有4个苹果，分成2：2称一次，也不能说最重的就在总重量较大的那两个中，因为还有可能轻的那一份是最重的和最轻的在一起，就好比4+5>6+2，4和5都小于6一样，因为每个都不一样，所以任何苹果的组合称重都不能说明其中个体的情况，最终还是要回到个体的比较，所以最优解就是一个一个比较，每次淘汰一个，19次后就出来最大的了

如果每个不一样重、无法通过其他辨识重量那就需要19次。如果是只有一个重的、第一次先一边7个、如果不一样重、重的苹果在重的那7个中、如果一样重、重的苹果在剩下的6个中，第二次：一边3个、同理一样重的话、剩下的那个是重的、不一样就是重的在3个重的那一边；如果第一步是剩下六个重、那就一边2个、能把重的直接定位到某两个；第三次：三个中找重的只需要一次、一边一个、那个重就是那个、一样重就是剩下的那个、所以只需要三次

人家说你就信呀，19次，不接受任何反驳

一次只比较2个苹果的遍历3-4次是不行的，19次才对。但如果是多个（大于2）一起比较选出最重的，然后再在剩下的苹果里再比较大小，那就可以减少次数，关键看你的需求

利用排序的思想去解决这个问题，只排除最大的，加上时间复杂度的思想去解决这个问题

问的是至少 所以可以存在特例条件 三次

1）不自己写程序，只能是19次才能确定最重的那个，细微的重量差别，你只能相信天平了，这是常识
2）自己写程序算法，最容易想到的是二分法，复杂度O(n/2)
3）3到4次是可能的，那就看你用什么数据结构存储：跳表，红黑树等，这是数据结构的事情了，再扩充就跑题了，哈哈

这个问题可以转换成算法问题。
排列数组中数字得出最大数算法

具体代码如下python

def get_max_num(given_list):
    max_len = len(str(max(given_list)))
    str_data = [(('{:'+str(item)[-1]+'<'+str(max_len)+'}').format(item), 
    len(str(item))) for item in given_list]
    print('tuple data= ', str_data)
    sorted_str = sorted(str_data, reverse=True)
    print('sort_data= ', sorted_str)
    decode_str = [sd[0][:sd[1]] for  sd in sorted_str]
    print('result= ', ''.join(decode_str))
 
get_max_num([9,99,77,123,8,78,76,7])

每个苹果都不一样重，我感觉就是19次了吧。二分啥的都不适用了吧

这玩意，每个都不一样重。
20个苹果，比19次，才能找到。

因为是天平秤，所以一次可以对2个苹果进行比重。
第一轮称10次可以淘汰10个苹果，第二轮5次可以从剩余的10个中再次淘汰5个，第三轮从剩下随机拿出一个轮空称其它4个需要2次，第四轮再次从剩下的3个苹果中随机拿出一个轮空称其它2个需要1次，第五轮称1次决出剩下的2个苹果哪个重。
所以需要10+5+2+1+1 需要19次。

19次是肯定可以的，3次，4次那是不可能的，特殊情况才成立。

最少通过3次就能找出来。原则是每次称的时候分为3堆来称。例如本题第1次称的时候，分成668三堆，把两堆各是6个的苹果放到天平上，如果一端轻了，说明要找的那个苹果在轻的那一堆里，如果一样重的话那么要找的那个苹果就在剩下的8个苹果那一堆里。假设在6个的那一堆中，第二次称同理分成222的三堆。把任意2个放天平两端，根据前面所述，很容易把轻的那2个找出来，那么只剩2个苹果了，再称1次就找到了。所以用了3次。如果第一次称完轻的那个苹果在8个那一堆里，用同样的方法，分成332三堆，也很容易一共通过3次就能找出来。

如果大小没有明显差别那么需要一个个的称，称19次，没别的办法，

怎么感觉这个提，我去面试公司，老总问过我😂😂

现实生活中你一次就能拿到最大的，如果差别大的话，一眼就看出来了
游戏中，你永远拿不到，除非写代码的让你拿到

不用遍历那么多次，将20个苹果看成是一个集合中的20个数据，可以对集合进行升序或降序排序，然后取出第一个或最后一个数据即可