如何在C++中求一个数组的中间数输出 |21xrx.com

如何在C++中求一个数组的中间数输出

2023-06-30 09:37:48 深夜i -- --

C++ 数组中间数排序输出

在C++中，对于一个数组，我们可以通过多种方式来求出其中间数。下面介绍两种简单的方法。

方法一：对数组进行排序，输出中间位置的元素值。

首先，需要使用C++中的sort函数对数组进行升序排序，然后找出中间位置的元素值。如果数组长度为奇数，则中间位置为(n-1)/2；如果数组长度为偶数，则中间位置为n/2-1和n/2两个位置的平均值。代码如下：


#include <iostream>
#include <algorithm> //包含sort函数
using namespace std;
int main() {
  int arr[] = 3;
  int n = sizeof(arr) / sizeof(arr[0]);
  sort(arr, arr + n); //升序排序
  int mid = n / 2;
  if (n % 2 == 0) {  //数组长度为偶数
    cout << "中间数为：" << (arr[mid-1] + arr[mid]) / 2 << endl;
  } else {      //数组长度为奇数
    cout << "中间数为：" << arr[mid] << endl;
  }
  return 0;
}

方法二：使用快速选择算法，求出数组中第n/2小的元素值，即为中间数。

快速选择算法基于快速排序，它通过一系列的分割操作将大问题转化为小问题，以此来寻找数组中第k小（或第k大）的元素，其中k为1到n之间的正整数。快速选择算法的时间复杂度为O(n)。

对于求解数组的中间数，我们只需要找到数组中第n/2小的元素值即可。代码如下：


#include <iostream>
using namespace std;
int partition(int arr[], int left, int right) {
  int pivot = arr[left]; //基准值
  while (left < right) {
    while (left < right && arr[right] >= pivot) right--; //从右往左扫描，找到第一个小于基准值的数
    arr[left] = arr[right]; //将其放到左边
    while (left < right && arr[left] <= pivot) left++; //从左往右扫描，找到第一个大于基准值的数
    arr[right] = arr[left]; //将其放到右边
  }
  arr[left] = pivot; //基准值归位
  return left;
}
int quickSelect(int arr[], int left, int right, int k) { //返回第k小的元素值
  if (left == right) return arr[left];
  int pivotIndex = partition(arr, left, right); //返回基准值的位置
  int cnt = pivotIndex - left + 1; //统计基准值左侧的元素个数
  if (cnt == k) { //第k小的元素就是基准值
    return arr[pivotIndex];
  } else if (cnt < k) { //第k小的元素在基准值右侧
    return quickSelect(arr, pivotIndex + 1, right, k - cnt);
  } else { //第k小的元素在基准值左侧
    return quickSelect(arr, left, pivotIndex - 1, k);
  }
}
int main() {
  int arr[] = {3, 5, 1, 4, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  int mid = n / 2;
  cout << "中间数为：" << quickSelect(arr, 0, n - 1, mid + 1) << endl;
  return 0;
}

无论是使用排序还是快速选择算法，都可以在C++中求出一个数组的中间数。选择哪种方法，主要取决于具体应用场景和数据规模。

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

下一篇: C++中的1.5f：浮点数表示方法

评论区

()

相似文章