C++求解前k大的数 |21xrx.com

C++求解前k大的数

2023-07-05 11:42:59 深夜i -- --

C++ 求解前k大数

在算法和数据结构中，求解前k大的数是一项常见的问题，通常是在一组数据中找出前k大的数据。这个问题在实际应用中也有很多场景，比如在网站的页面排名中，需要将页面访问量前k的页面进行展示。

在C++中，我们有多种方法来解决这个问题。下面我们将介绍两种常用的方法。

方法1：冒泡排序

冒泡排序是一个简单但效率较低的排序算法，在这个问题中也可以使用它来解决。我们可以将数据按照从大到小的顺序进行排序，然后取出前k个数即可。

代码如下：

void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] < arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}
void printTopK(int arr[], int n, int k) {
  bubbleSort(arr, n);
  for (int i = 0; i < k; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

方法2：堆排序

堆排序是一种较为高效的排序算法，我们可以使用最小堆来解决这个问题。

我们可以使用一个大小为k的最小堆来存储数据，当堆的大小小于k时，将数据插入到堆中；当堆的大小等于k时，如果新的数据大于堆顶，就弹出堆顶并插入新的数据。最后堆中剩余的元素就是前k大的数。

代码如下：

void printTopK(int arr[], int n, int k) {
  priority_queue<int, vector<int>, greater<int>> minHeap;
  for (int i = 0; i < n; i++) {
    if (minHeap.size() < k) {
      minHeap.push(arr[i]);
    } else if (arr[i] > minHeap.top()) {
      minHeap.pop();
      minHeap.push(arr[i]);
    }
  }
  while (!minHeap.empty()) {
    cout << minHeap.top() << " ";
    minHeap.pop();
  }
  cout << endl;
}

综上所述，我们可以使用冒泡排序或堆排序来解决求解前k大的数的问题。堆排序的效率要比冒泡排序高，所以在大规模数据的应用中，建议使用堆排序。

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

下一篇: VC++6.0 简单代码示例

评论区

相似文章