数组中最小的两个数

Question

问题很简单（答案也很简单）： 如何找到一个数组中的前两个最小数？

  for ( i = 1; i <= n ; i++){
        if(v[i] < maxim)
        maxim = v[i];
                            }
  cout << maxim;

我能想到的唯一办法是它只会给我展示最小值，而不是前两个最小值。

- griffinwish

---

http://www.geeksforgeeks.org/to-find-smallest-and-second-smallest-element-in-an-array/ - Kamlesh Arya

简单的方法是对数组进行排序，然后可以相当容易地访问最低的 n 个项。您还可以引入一个额外的变量来存储第二个最低的数字。 - martijnn2008

对数组进行排序需要编写相当多的代码行，我该如何引入第二个变量？ - griffinwish

调用std::sort可以在一行代码中完成，这样的代码甚至更少 :) http://www.cplusplus.com/articles/NhA0RXSz/ 那第二个变量正是@KamleshArya使用他的链接所建议的（请参见上面的评论）。 - martijnn2008

请注意，C/C++数组是以0为索引的。因此，您的循环应该是for (int i = 0; i < n ; i++)。 - Jarod42

@martijnn2008：std::nth_element 也是一行代码，而且渐近最优。 - Nemo

Answer 1

如果你的数组可能会发生变化，你可以使用 std::partial_sort：

std::partial_sort(v, v+2, v+n);

那么，v [0] 和 v [1] 是 v 中最小的两个值。

如果不打算更改数组或应避免更改，则 std :: partial_sort_copy 是您的好帮手。引入一个新的两个元素的数组，将其中的最小值写入其中：

<code><code><code>int minima[2];
std::partial_sort_copy(v, v+n, minima, minima+2);
</code></code></code>

请根据需要更改 minima 数组的类型。我不知道您的数组 v 的类型。

要使用这些函数，您必须包含以下文件：

#include <algorithm>

- leemes

---

我不熟悉std::的含义，甚至不熟悉那个（函数？）partial_sort_copy。 - griffinwish

是的，它是一个函数。std::表示它是C++标准库的一部分，其中包含许多有用的构建块。 - leemes

@griffinwish，如果你从像“Hello World”这样的基础开始学习，会不会更好呢？ - sam

@martijnn2008 不是的。STL 是现在标准库的一部分的前身。它是一个不同的库的名称。 - leemes

我只是想知道为什么人们不使用using namespace std而是到处写std::。 - griffinwish

Answer 2

另一个简单的方法是...

int v[] = {33,11,22,3};
int secmaxim = INT_MAX-1;
int maxim = INT_MAX;
    for ( int i = 0; i < 4 ; i++){
        if(v[i] < maxim)
        {
             secmaxim = maxim;
             maxim = v[i];
        }
    else if(v[i] < secmaxim && v[i] != maxim)
            secmaxim = v[i];
 }
  cout << maxim << secmaxim;

- HadeS

---

这种方法比排序还要快。作为初学者，你可能还不太关心这个，但是随着时间的推移，你会注意到的。 - Beta

@Beta 当适当时，您应该选择最快的代码（而不是可读性、简单性和可重用性），而不是过早地选择。作为初学者，您可能还不关心这一点，但随着时间的推移，您会明白其重要性。 - leemes

此外，这段代码是错误和不完整的。数组索引偏移了一个位置，并且没有显示出两个引入变量的初始化。 - leemes

我认为在初级阶段，应该尝试提高自己的问题解决能力......我们在这里讨论了解决这个问题的两种方法......你仍然可以找到其他解决这个问题的方法.. :-).. - HadeS

如果出现重复，你的结果可能会很奇怪。 - Jarod42

Answer 3

如何在C++中找到数组的前k个最小元素。

朴素方法：调用std::sort；查看前k个元素。运行时间为O(n log n)。

面试题方法：循环遍历数组，使用一个大小为k的std::set（或std::push_heap和pop_heap）来跟踪最小的k个元素。运行时间为O(n log k)。此方法不修改数组，按顺序返回结果，并且仅使用O(k)的额外空间。

最佳方法：#include。std::nth_element(&a[0], &a[k], &a[n])。查看前k个元素。运行时间为O(n)，这是最优的。

[更新]

我觉得我应该解释一下我所说的“面试题方法”。如果你在面试中真的被问到这个问题，你可能在Google、Amazon或其他大数据环境中，面试官可能会说：“我有1000亿个整数在磁盘上，我想知道其中最小的1000个。”在这种情况下，修改数组或需要O(n)额外空间的解决方案可能不是最好的选择。

- Nemo

Answer 4

你可以使用 std::sort() 来对元素进行排序。

以下是一个小例子，展示 sort 如何工作？

#include <iostream>
#include <array>
#include <algorithm>

int main() {
    std::array<int, 5> arr {5,3,24,9,7};

    std::sort(arr.begin(), arr.end());

    std::cout << arr[0] << std::endl << arr[1];

    return 0;
}

在上面的代码中，std::sort将按升序对数组arr进行排序。使用sort需要包含头文件<algorithm>。

输出结果为：

3

5

这里是上述代码的可工作版本链接。

- sam

---

这是不必要的低效率。 - juanchopanza

@juanchopanza 同意它是 O(n log(n))，但是 OP 没有要求最快的解法，所以我发了一个替代方案 :) - sam

Answer 5

在不改变数组顺序的情况下，

#include <iostream>
#include <vector>
#include <algorithm>

int main( )
{
    std::vector<int> v {9, 8, 7, 6, 5, 1, 2, 3, 4};

    int smallest        = *std::min_element(v.begin(), v.end());
    int second_smallest = *std::min_element(v.begin(), v.end(), [&smallest](int i, int j) { return i < j && i >= smallest; });

    std::cout << "smallest: "        << smallest        << std::endl;
    std::cout << "second smallest: " << second_smallest << std::endl;
}

输出：

smallest: 1
second smallest: 2

- Achilles Rasquinha

Answer 6

改编自@leemes的答案（使用更现代的语法），详见他的答案解释。

const auto topVals = 2;
std::array<int, topVals> minima;

std::partial_sort_copy(std::begin(v), std::end(v), minima.begin(), minima.end());

- FToDance

---

这不是一个答案。 - juanchopanza

我知道...这本来应该是对@leemes答案的评论，但我没有足够的声望... - FToDance

那不重要。这并不改变这不是一个答案的事实。 - juanchopanza

再次强调，对于这个问题来说，std::nth_element 更加合适（而且速度更快）。 - Nemo

@WesleyShillingford：(a) 他没有说结果必须有序。(b) 如果您无法修改原始数组并希望结果有序，则应使用仅需要O(k)附加空间的集合或二进制堆。 （请参见我的答案。）简而言之，无论您的假设如何，此答案都是劣质的。 - Nemo