使用C ++标准库函数在线性时间中查找未排序数组的中位数
先决条件：C++中的std::nth_element()
问题陈述：
查找未排序数组的中位数。
什么是中位数？
中位数是一种统计量度，将有序数据集分为两半。中位数是任何有序列表的分区点。在排序数组的情况下，中值是中间元素。如果数组大小为奇数，则中位数仅是中间元素；如果数组大小为奇数，则中位数为两个中间元素的平均值。
示例
具有奇数大小的数组：
array= [5, 4, 3, 1, 2] If the array was sorted then it would be [1,2,3,4,5] and the middle element would be 3 Thus the median is 3
大小均匀的数组：
array= [5, 4, 3, 1, 2, 6] If the array was sorted then it would be [1, 2, 3, 4, 5, 6] and the middle element would be 3 & 4 Thus the median is (3+4)/2 = 3.5
因此，要找到未排序数组的中位数，我们需要在对数组进行排序时找到中间元素。我们不需要对整个数组进行排序，如果数组已排序，则只需要中间元素即可。
为此，我们可以使用标准库中的nth_element()函数，如果对数组进行了排序，则该函数会给出nth_element()。
因此，算法为：
如果数组大小为奇数：
我们只需要中间元素sorted_array[n/2]，其中n是元素的数量，sorted_array是数组的排序版本。但是我们不需要使用数组，而是像下面这样使用，
nth_element(array.begin(),array.begin()+n/2,array.end()) Where, array.begin()=start iterator to the array array.end()=End iterator to the array So the range is from start tio end the entire array arr.begin()+n/2 = iterator to our desired nth element After this array[n/2] will give us the middle element if array was sorted which is median itself since size is odd.
如果数组大小是偶数：
我们需要中间元素是第n/2个元素和第（n/2-1）个元素。
和以前一样，我们做到了。
寻找第n/2个元素
nth_element(array.begin(),array.begin()+n/2,array.end()) store array[n/2] to variable a To find (n/2-1)th element nth_element(array.begin(),array.begin()+(n-1)/2,array.end()) store array[n/2] to variable b So, the median would be (a+b)/2.0 Remember don't leave doing integer division as that will lead to wrong answer. That's why divide by 2.0 not 2
示例
#include <bits/stdc++.h>
using namespace std;
//打印矢量
void print(vector<int> arr)
{
for (auto it : arr) {
cout << it << " ";
}
cout << endl;
}
int main(){
int n;
cout << "Enter number of input elements \n";
cin >> n;
//看看它是如何初始化的
cout << "Input the elements\n";
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Printing the array initially...\n";
print(arr);
//数组大小为奇数
if (n % 2 == 1) {
//如果数组已排序，则中位数为arr[n/2]
//做同样的事情
nth_element(arr.begin(), arr.begin() + n / 2, arr.end());
cout << "//中位数是： " << arr[n / 2] << endl;
}
else { //数组大小甚至
//位数是ARR[N/2-1]+ARR[N/2]如果数组进行排序
//第n/2个元素
nth_element(arr.begin(), arr.begin() + n / 2, arr.end());
int a = arr[n / 2];
//第n/2-1元素
nth_element(arr.begin(), arr.begin() + n / 2 - 1, arr.end());
int b = arr[n / 2 - 1];
cout << "//中位数是： " << (a + b) / 2.0 << endl;
}
return 0;
}输出：
RUN 1: Enter number of input elements 5 Input the elements 5 4 3 1 2 Printing the array initially... 5 4 3 1 2 //中位数是： 3 RUN 2: Enter number of input elements 6 Input the elements 6 5 4 1 2 3 Printing the array initially... 6 5 4 1 2 3 //中位数是： 3.5