c++ 给定一个非常巨大的数组，如何找到它的中值

快速选择算法（最优解） 

#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. 不需要修改原数组。

缺点是结果是近似值，不是精确的中位数。精确度可以通过增加桶的数量来提高，但会增加空间复杂度。