-3

如何打印此列表中最高的 10 个数字？

这是我的数字列表，我是编程新手，我知道我必须使用数组，但之后我不确定。

     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
4

7 回答 7

4

您将需要std::partial_sort结合operator>.

于 2013-03-27T16:17:11.653 回答
1

如果将这些数字保存在向量中，则可以使用 std::sort()

于 2013-03-27T16:14:52.520 回答
0

将您的数字放入一个数组中（理想情况下读取文件中的数字列表）按降序对数组进行排序（使用现有函数，如其他答案所建议的那样，或者，我猜这是一个课程练习，通过使用解释的算法在课堂上) for (i = 0; i<10; i++) print array[i];

抱歉，它开始看起来像代码...

于 2013-03-27T16:17:53.987 回答
0

首先对数组进行排序。

获取数组的大小，并将其用作索引。然后写一个for循环，如：

for(int index = size -1; index >=0; index--) 
    // print here
于 2013-03-27T16:18:55.613 回答
0

以下应该有效：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
  std::vector<int> v;
  for(unsigned i = 0; i < 100; ++i) {
     v.push_back(i);
  }
  std::random_shuffle(v.begin(), v.end());

  std::partial_sort(v.begin(), v.begin() + 4, v.end());
  for(unsigned k = 0; k < 4; ++k) {
    std::cout << k << "-th element is " << v[k] << '\n';
  }
}

正如其他人已经指出的那样，关于复杂性的说明。在这种情况下使用 partial_sort通常会更好，因为它对这种情况具有更好的复杂性。但是，如果您只是玩玩具实例，那么完整的排序也可以解决您的问题。

下一次，展示更多的努力，比如你尝试过的代码和你在文献中找到的东西等。

于 2013-03-27T16:46:57.917 回答
0

您可以通过以下几种方式做到这一点：假设您的列表中有 N 个元素，并且您必须选择 X 个最高的元素。1）对数组进行排序，然后选择 X 个最高元素元素。现在，由于排序将花费 O(NlogN) 时间，而您的选择将花费 O(X) 时间，因此总体复杂度将为 O(NlogN)。

2）不要对数组进行排序，只需遍历列表以找到最高元素，然后再次遍历以找到下一个最高元素，依此类推，直到获得 X 个最高元素。复杂度 O(X*N)，当 X < logN 时，最后一种方法更好。

3）您可以通过使用固定（X）大小的最大堆优化方法2，如果它们大于最大堆中的最小元素，则遍历列表将元素插入列表。复杂度 O(NLogX)。

于 2013-03-27T16:45:12.977 回答
0

如果列表很大，使用sort效率不是很高，因为您只想找到10最大的元素。更好的方法是用10元素构建一个最小堆，当堆大小小于 时10，将元素插入堆中。之后，当新元素到来时，将元素与堆的根进行比较，如果元素大于根，则插入堆并移除当前堆头，重复此过程，直到扫描完列表中的所有元素。该算法适用于时间复杂度“O(nlogk)”，其中n是元素的总数，k在这种情况下为 10。O(nlogn)如果您使用排序，效率会更高。您需要了解二进制堆在 C++ 中的工作原理，并且可以应用标准容器来实现一个非常容易为您工作的容器。

但是，使用std::sort是蛮力的方式，易于理解。

于 2013-03-27T16:33:43.760 回答