如何查找n值的中位數不使用數組（或列表或任何其他使用數組/列表的集合/函數）？

Question

場景：

用戶應該輸入N（值的數量） 後跟N個值。

如何輸出中位數？

Answer 1

你肯定需要一些存儲空間至少有N/2個地方。這是沒有辦法的。

編輯完成後OP的COMENT：

獲取有關節目一些好的當然，ESP。數據結構。你不能依賴Stackoverflow來開發你的所有開發職業;-)。說了這麼多，讓我們給你一個起點：我想在這裏使用ArrayList：

int n = ...; // get N from the user; 
List<Double> list = new ArrayList<Double>(); 
for (int i=0; i<n; i++) { 
    double element = ...; // get element from the user; 
    list.add(element); 
} 
// Have the Java library sort the list for you 
Collections.sort(list); 
// now pick/compute the median from the sorted list 
// I'll leave that up to you.. 

Answer 2

我建議你用手程序的二進制樹。您可能需要允許重複項，以便在內置的TreeSet中不會執行Java。也可能是你可以在網上的某處找到合適的樹實現。樹應該被排序。請參閱Binary search tree on Wikipedia獲取更多靈感。

您的主程序將逐個讀取您的數字並將它們插入到您的樹中。之後，如果N是偶數，它將查詢樹的中間元素，或者兩個中間元素。你不需要任何數組來實現你的樹。爲了找到第i個元素，樹會執行遍歷計數遇到的元素並返回第i個元素。

快樂編碼。

Answer 3

無Array，無List或任何其他Collection。

try (Scanner scanner = new Scanner(System.in)) { 
     System.out.print("Number of numbers: "); 
     int N = scanner.nextInt(); 
     System.out.printf("Enter the %d numbers: ", N); 
     double median = IntStream.range(0, N) 
       .mapToDouble(i -> scanner.nextDouble()) 
       .sorted() 
       .skip((N-1)/2) 
       .limit(2-N%2) 
       .average() 
       .getAsDouble(); 
     System.out.printf("The median is %f%n", median); 
    } 

（不注意的.sorted()幕後那個人。）