如何在C++中解决这个中值编程问题

在C++中解决中值编程问题，可以使用以下方法：

使用STL库中的nth_element函数。nth_element函数可以在O(n)时间复杂度内找到一个序列中的第n小或第n大的元素。

#include<iostream>
#include<vector>
#include<algorithm>

int find_median(std::vector<int>& nums) {
    int n = nums.size();
    if (n % 2 == 0) {
        return (nums[n/2 - 1] + nums[n/2]) / 2;
    } else {
        return nums[n/2];
    }
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    int median = find_median(nums);
    std::cout << "Median: "<< median<< std::endl;
    return 0;
}

使用快速选择算法。快速选择算法可以在O(n)时间复杂度内找到一个序列中的第k小或第k大的元素。

#include<iostream>
#include<vector>
#include<algorithm>

int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[left];
    int i = left + 1;
    int j = right;
    while (true) {
        while (i <= j && nums[i]< pivot) {
            i++;
        }
        while (i <= j && nums[j] > pivot) {
            j--;
        }
        if (i <= j) {
            std::swap(nums[i], nums[j]);
        } else {
            break;
        }
    }
    std::swap(nums[left], nums[j]);
    return j;
}

int quick_select(std::vector<int>& nums, int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }
    int pivot_index = partition(nums, left, right);
    if (k == pivot_index) {
        return nums[k];
    } else if (k< pivot_index) {
        return quick_select(nums, left, pivot_index - 1, k);
    } else {
        return quick_select(nums, pivot_index + 1, right, k);
    }
}

int find_median(std::vector<int>& nums) {
    int n = nums.size();
    if (n % 2 == 0) {
        return (quick_select(nums, 0, n - 1, n/2 - 1) + quick_select(nums, 0, n - 1, n/2)) / 2;
    } else {
        return quick_select(nums, 0, n - 1, n/2);
    }
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    int median = find_median(nums);
    std::cout << "Median: "<< median<< std::endl;
    return 0;
}

这两种方法都可以在O(n)时间复杂度内找到一个序列中的中值。