C++求中位数 |21xrx.com

C++求中位数

2023-07-07 09:19:05 深夜i 22 0

C++ 求解中位数

如果你正在学习C++编程语言，那么你一定要学习如何求中位数。中位数是一组数据中的中间数。对于一个包含偶数个元素的数据集，中位数是中间两个数的平均值。对于一个包含奇数个元素的数据集，中位数是该集合中的中间元素。这是一个重要的统计概念，在许多领域，如经济学、医学和计算机科学中都有广泛的应用。

下面是几种方法来求解C++中的中位数：

方法1：使用sort（）函数

使用sort（）函数可以将数组排序，然后得出中位数，如果有偶数个元素，则中位数为中间的两个元素的平均值，如果有奇数个元素，则中位数是中间元素的值。这是一种非常简单的方法，可以用下面的代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int a[10] = 1;
  sort(a, a+10);
  int n = sizeof(a) / sizeof(int);
  int median = 0;
  if(n%2==0)
  {
    median = (a[n/2 - 1] + a[n/2]) / 2;
  }
  else
  {
    median = a[n/2];
  }
  cout<<"数组的中位数是："<<median<<endl;
  return 0;
}

方法2：使用快速选择算法

快速选择算法是一种基于分治法的选择算法，与快速排序相似。该算法的主要思想是使用快排的分区方法来快速找到想要的元素。该方法的时间复杂度为O(n)，更快一些。

下面是使用快速选择算法来求解中位数的C++代码：

#include<iostream>
#include<algorithm>
using namespace std;
int partition(int a[], int l, int r)
{
  int pivot = a[r];
  int i = l-1;
  for(int j = l; j < r; j++)
  {
    if(a[j] <= pivot)
    {
      i++;
      swap(a[i], a[j]);
    }
  }
  swap(a[i+1], a[r]);
  return i+1;
}
int kthSmallest(int a[], int l, int r, int k)
{
  if(k>0 && k<=r-l+1)
  {
    int pos = partition(a, l, r);
    if(pos-l == k-1)
    {
      return a[pos];
    }
    if(pos-l > k-1)
    {
      return kthSmallest(a, l, pos-1, k);
    }
    return kthSmallest(a, pos+1, r, k-pos+l-1);
  }
  return INT_MAX;
}
int main()
{
  int a[10] = 1;
  int n = sizeof(a) / sizeof(int);
  int median = kthSmallest(a, 0, n-1, n/2 + 1);
  cout<<"数组的中位数是："<<median<<endl;
  return 0;
}

在以上代码中使用了快速选择算法，这种算法的时间复杂度为O(n)。最终，我们得到了该数组的中位数。

在C++中，求中位数有多种方法。使用sort（）函数会将数组排序并返回中位数；使用快速选择算法可以更快地找到中位数。无论是哪种方法，都可以在C++中进行实现。希望本篇文章的内容能够对您有所帮助。

上一篇: idea打包java可执行jar包

下一篇: Go语言和C++语言的异同

评论区

相似文章