快速選擇算法（最優解）?

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;class Solution {
private:// 快速選擇算法中的分區函數int partition(vector<int>& nums, int left, int right) {int pivot = nums[right]; // 選擇最右邊的元素作為樞紐元int i = left - 1; // i 指向小于等于 pivot 的元素for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums[i], nums[j]); // 將小于等于 pivot 的元素交換到左側}}swap(nums[i + 1], nums[right]); // 將 pivot 放到正確的位置return i + 1; // 返回 pivot 的索引}// 快速選擇算法int quickSelect(vector<int>& nums, int left, int right, int k) {if (left == right) return nums[left]; // 只有一個元素，直接返回int pivotIndex = partition(nums, left, right); // 獲取 pivot 的索引if (k == pivotIndex) {return nums[k]; // 找到第 k 個最大元素} else if (k < pivotIndex) {return quickSelect(nums, left, pivotIndex - 1, k); // 在左側繼續查找} else {return quickSelect(nums, pivotIndex + 1, right, k); // 在右側繼續查找}}public:double findMedian(vector<int>& nums) {int n = nums.size();if (n % 2 == 1) {return quickSelect(nums, 0, n - 1, n / 2); // 奇數個元素，直接找到中位數} else {int left = quickSelect(nums, 0, n - 1, n / 2 - 1); // 找到第 n/2-1 個最大元素int right = quickSelect(nums, 0, n - 1, n / 2); // 找到第 n/2 個最大元素return (left + right) / 2.0; // 計算中位數}}
};int main() {vector<int> nums = {3, 2, 1, 5, 6, 4};Solution sol;double median = sol.findMedian(nums);cout << "中位數是：" << median << endl;return 0;
}

?如果數組太大，無法一次性加載到內存中，或者我們不能修改原數組，可以考慮使用基于分塊的近似算法：

基于分塊的近似算法（適用于超大數據集）

class Solution {
public:double findApproximateMedian(const vector<int>& nums) {const int BUCKET_SIZE = 1000;  // 可以根據實際情況調整vector<int> count(BUCKET_SIZE, 0);int minVal = INT_MAX, maxVal = INT_MIN;// 第一次遍歷：找到最小值和最大值for (int num : nums) {minVal = min(minVal, num);maxVal = max(maxVal, num);}double bucketSize = (maxVal - minVal + 1.0) / BUCKET_SIZE;// 第二次遍歷：統計每個桶的元素數量for (int num : nums) {int index = min((int)((num - minVal) / bucketSize), BUCKET_SIZE - 1);count[index]++;}// 找到中位數所在的桶int medianCount = (nums.size() + 1) / 2;int bucketIndex = 0;int sum = 0;while (sum < medianCount) {sum += count[bucketIndex];bucketIndex++;}bucketIndex--;// 計算近似中位數double medianLow = minVal + bucketIndex * bucketSize;double medianHigh = minVal + (bucketIndex + 1) * bucketSize;return (medianLow + medianHigh) / 2.0;}
};

這個算法的優點：

1. 只需要兩次遍歷數組。
2. 空間復雜度是O(1)，因為使用了固定大小的桶。
3. 可以處理非常大的數據集，甚至是流數據。
4. 不需要修改原數組。

缺點是結果是近似值，不是精確的中位數。精確度可以通過增加桶的數量來提高，但會增加空間復雜度。