Use the least number of comparisons to get the largest and 2nd largest number in the given integer array. Return the largest number and 2nd largest number.

Assumptions

• The given array is not null and has length of at least 2

Examples

• {2, 1, 5, 4, 3}, the largest number is 5 and 2nd largest number is 4.

Solution: 每次两两比较，找到较大的数，然后把较小的数放在较大的数的smaller list里，最后在最大的数的smaller list里找次大的。比较n + log n次

  public int[] largestAndSecond(int[] array) {
    Node[] nodes = new Node[array.length];
    for (int i = 0; i < array.length; i++) {
      nodes[i] = new Node(array[i]);
    }
    int largerLength = array.length;
    while (largerLength > 1) {
      for (int i = 0; i < largerLength / 2; i++) {
      //使得数组的前一半是较大的数
        if (nodes[i].val < nodes[largerLength - 1 - i].val) {
          Node temp = nodes[i];
          nodes[i] = nodes[largerLength - 1 - i];
          nodes[largerLength - 1 - i] = temp;
        }
        //较小的放在较大的list里
        nodes[i].smaller.add(nodes[largerLength - 1 - i].val);
      }
      largerLength = (largerLength + 1) / 2;
    }
    int second = Integer.MIN_VALUE;
    for (int num : nodes[0].smaller) {
      second = Math.max(second, num);
    }
    return new int[]{nodes[0].val, second};
  }
  class Node {
    int val;
    List<Integer> smaller;
    public Node(int x) {
      val = x;
      smaller = new ArrayList<>();
    }
  }