在C++中解决中值编程问题,可以使用以下方法:
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;
}
#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)时间复杂度内找到一个序列中的中值。
领取专属 10元无门槛券
手把手带您无忧上云