arrays - 仅需 9 次比较即可在 8 个数字的数组中找到最小和第二小的数字

Question

这是我必须回答的面试问题。好吧，实际上是一个 friend ，但他问了我，我也不知道答案。因此我在这里问:

给定一个包含 8 个整数的数组，仅使用 9 次比较即可找到最小和第二小的整数。更具体地说，在 n+log(n)-2 时间内。

我知道您如何仅使用 9 次比较就可以做到这一点。这就是我接近它的程度。 (10 次比较)

public class Comp {
    static int[] nums = new int[]{9, 4, 5, 3, 2, 7, 6, 1};
    static int compcount = 0;

    //int[] is nums[] array
    public static int[] twoLeast(int[] a){
        int min1 = a[0]; //Prospective lowest number
        int min2 = a[1]; //Prospective second lowest number

        if(isLessThan(min2, min1)){
            min1 = a[1];
            min2 = a[0];
        }

        for(int i=2; i<a.length;i++){
            if(isLessThan(a[i], min1)){
                min2 = min1;
                min1 = a[i];
            }else if(isLessThan(a[i], min2)){
                min2 = a[i];
            }
        }

        return new int[]{min1, min2};
    }

    public static boolean isLessThan(int num1, int num2){
        compcount++;
        return num1 < num2;
    }
}

这里我有一个函数 isLessThan() 来跟踪比较次数。同样，这会进行 10 次比较。 9个比较怎么可能做到。还是 n+log(n)-2 时间？

P.S: 我是用java实现的，但它可以是任何语言

Answer 1

一种思考解决方案的方法是，这就像一场网球淘汰赛系列赛。假设每个数字对应一个玩家。将数字配对，让每个游戏对应一对数字之间的比较:

游戏:(a1,a2)、(a3, a4)、(a5, a6)、(a7, a8)

获胜者:a12、a34、a56、a78

游戏:(a12, a34) , (a56, a78)

获胜者:a1234、a5678

游戏:(a1234, a5678)

获胜者:a12345678

游戏数=7 ==> (n - 1)

第二名将仅被获胜者击败。假设 a3 是赢家。那么第二好的将是 a4 ， a12 或 a5678 。

游戏:(a4, a12)

获胜者:a412

游戏:a(412, 5678)

获胜者:a4125678

所以我们有第二好的 2 游戏 ==> (lg(n) - 1)

因此游戏数量 = 7 + 2 = 9 = (n + lg(n) - 2)

这更容易将上述竞争形象化为一棵树:

               a12345678
              /         \
             /           \
            /             \
           /               \
        a1234            a5678
       /     \           /    \
      /       \         /      \
   a12       a34      a56      a78
  /   \     /   \    /   \    /  \
a1     a2  a3   a4 a5    a6  a7   a8

如果 a3 获胜，我们有:

                   a3
                   |
              /----|----\
             /           \
            /             \
           /               \
          a3 >==========> a5678
       /     \           /    \
      /       \         /      \
   a12 <====< a3      a56      a78
  /   \     /   \    /   \    /  \
a1     a2  a3 ->a4 a5    a6  a7   a8

基本上，最终获胜者 a3 将遍历一条从叶节点到根节点 (lg(n) -1) 的路径。在他的道路上，他将击败第二好的选手，即 {a4, a12, a5678} 之一。因此，我们可以通过查看路径中除获胜者之外的最大值来找出谁是第二好的，正如所描述的那样。