使用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)); 
}