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

Assumptions

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

Examples

• {2, 1, 5, 4, 3}, the largest number is 5 and smallest number is 1. return [5, 1].

Solution: 先两两比较，找出max list和min list，再分别在里面找largest和smallest。比较3n/2次

  public int[] largestAndSmallest(int[] array) {
    List<Integer> max = new ArrayList<>();
    List<Integer> min = new ArrayList<>();
    for (int i = 0; i < array.length; i += 2) {
      if (i + 1 < array.length) {
        max.add(Math.max(array[i], array[i + 1]));
        min.add(Math.min(array[i], array[i + 1]));
      } else {
        max.add(array[i]);
        min.add(array[i]);
      }
    }
    int largest = array[0], smallest = array[0];
    for (int cur : max) {
      largest = Math.max(largest, cur);
    }
    for (int cur : min) {
      smallest = Math.min(smallest, cur);
    }
    return new int[]{largest, smallest};
  }

a better way to write it: 头尾比较，swap，使前一半max，后一半min（省空间）