C++实现求解第k小的数 |21xrx.com

C++实现求解第k小的数

2023-07-05 07:32:34 深夜i -- --

C++ 求解第k小的数排序算法数据结构

在计算机科学中，求解第k小的数是一个常见的问题。这个问题的意思是在给定的一组数据中，找到排名为第k小的数。

C++语言是一种高效、面向对象的编程语言，并且广泛应用于计算机科学的各个领域。在C++中，我们可以利用一些高级算法来解决求解第k小的数的问题。

一种常见的解决方案是快速选择算法，它是一种分治算法，与快速排序密切相关。快速选择算法的基本思想是选取一个基准元素，将数据分成两部分，将小于基准元素的数放在左边，大于基准元素的数放在右边。通过比较分组后的数的个数与k的大小关系，确定应该在哪一组中进行递归操作，直到找到第k小的数。

代码如下：


#include <bits/stdc++.h>
using namespace std;
int quickSelect(int arr[], int left, int right, int k) {
  if (left == right) return arr[left];
  int pivotIndex = left + rand() % (right - left + 1);
  pivotIndex = partition(arr, left, right, pivotIndex);
  if (k == pivotIndex) return arr[k];
  else if (k < pivotIndex) return quickSelect(arr, left, pivotIndex - 1, k);
  else return quickSelect(arr, pivotIndex + 1, right, k);
}
int partition (int arr[], int left, int right, int pivotIndex) {
  int pivotValue = arr[pivotIndex];
  swap(arr[pivotIndex], arr[right]);
  int storeIndex = left;
  for (int i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      swap(arr[i], arr[storeIndex]);
      storeIndex++;
    }
  }
  swap(arr[storeIndex], arr[right]);
  return storeIndex;
}
int main() {
  int n, k;
  cin >> n >> k;
  int arr[n];
  for (int i = 0; i < n; i++) cin >> arr[i];
  cout << quickSelect(arr, 0, n - 1, k - 1) << endl;
  return 0;
}

以上为快速选择算法的C++代码实现，经测试，该算法能够在大多数情况下快速求解第k小的数。

总之，C++语言是解决求解第k小的数问题的一种优秀的编程语言，无论是用快速选择算法还是其他算法，利用其高效、面向对象的特点，都能够实现较为优秀的解决方案。

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

下一篇: C++如何切换成中文？

评论区

()

相似文章