使用3n/2比较找出最大和最小元素？

Question

我想设计一个算法，给定n个元素的列表，找到3n/2比较中的最小值和最大值。如何做到这一点的任何提示？

Answer 1

作为一个提示，想象一下所有阵列元素都是淘汰赛中的球员。将所有球员配对，让“赢家”（更大的数字）晋级一场比赛，而“输家”（较小的数字）则落入输家的支架。您现在将有n/2个获胜者考虑，最大值必须是其中的一个，并考虑n/2个失败者，最小值必须是其中之一。在这样做的过程中，你做了n/2次比较。你能用余下的n个比较来找出一组的最小值和另一组的最大值？

Answer 2

@templatetypedef的提示是正确的：

public static void findMinimumAndMaximumOf(int[] numbers) { 
    assert numbers.length >= 2; 
    List<Integer> bigList = new ArrayList<>(numbers.length/2); 
    List<Integer> smallerList = new ArrayList<>(numbers.length/2); 
    int i = 1; 
    for (; i < numbers.length; i = i + 2) { 
     if (numbers[i] > numbers[i - 1]) { 
      bigList.add(numbers[i]); 
      smallerList.add(numbers[i - 1]); 
     } else { 
      bigList.add(numbers[i - 1]); 
      smallerList.add(numbers[i]); 
     } 
    } 
    if ((numbers.length & 1) == 1) { 
     if (numbers[numbers.length - 1] > numbers[numbers.length - 2]) { 
      bigList.add(numbers[numbers.length - 1]); 
     } else { 
      smallerList.add(numbers[numbers.length - 1]); 
     } 
    } 
    Iterator<Integer> iBig = bigList.iterator(); 
    int biggest = iBig.next(); 
    while (iBig.hasNext()) { 
     int current = iBig.next(); 
     if (current > biggest) { 
      biggest = current; 
     } 
    } 
    Iterator<Integer> iSmall = smallerList.iterator(); 
    int smallest = iSmall.next(); 
    while (iSmall.hasNext()) { 
     int current = iSmall.next(); 
     if (current < smallest) { 
      smallest = current; 
     } 
    } 
    System.out.println(String.format("Max:%d, Min:%d" ,biggest,smallest)); 
}