21xrx.com
2024-11-05 17:24:48 Tuesday
登录
文章检索 我的文章 写文章
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大的数的问题。堆排序的效率要比冒泡排序高,所以在大规模数据的应用中,建议使用堆排序。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复