如何高效地从数组中找到第二大的数？

Question

如何在只遍历一次整个数组的情况下找到一个整数数组中第二大的数？

例如，我有一个由五个整数组成的数组，我想找出其中第二大的数。以下是我在面试中尝试过的一种方法：

#define MIN -1
int main()
{
    int max=MIN,second_max=MIN;
    int arr[6]={0,1,2,3,4,5};
    for(int i=0;i<5;i++){
        cout<<"::"<<arr[i];
    }
    for(int i=0;i<5;i++){
        if(arr[i]>max){
            second_max=max;
            max=arr[i];          
        }
    }
    cout<<endl<<"Second Max:"<<second_max;
    int i;
    cin>>i;
    return 0;
}

然而，面试官提出了一个测试用例int arr[6] = {5,4,3,2,1,0};，这将防止它第二次进入if条件。我告诉面试官唯一的方法是对数组进行两次解析（两个for循环）。有没有更好的解决方案？

- Xinus

---

在查找第二大的过程中，数组是否被重新排序会有影响吗？ - Martin

使用堆结构代替数组或使用有序数组结构。 - gaussblurinc

Answer 1

你将max和second_max初始化为-1是有缺陷的。如果数组中有像{-2，-3，-4}这样的值怎么办？

相反，你可以取数组的前两个元素（假设数组至少有两个元素），比较它们，将较小的赋给second_max，将较大的赋给max：

if(arr[0] > arr[1]) {
 second_max = arr[1];
 max = arr[0];
} else {
 second_max = arr[0];
 max = arr[1];
}

从第三个元素开始比较，根据需要更新max和/或second_max：

for(int i = 2; i < arr_len; i++){
    // use >= n not just > as max and second_max can hav same value. Ex:{1,2,3,3}   
    if(arr[i] >= max){  
        second_max=max;
        max=arr[i];          
    }
    else if(arr[i] > second_max){
        second_max=arr[i];
    }
}

- codaddict

---

关于负数，你说得对。但是如果最大的数出现了两次，你的代码会使第二大的数等于最大的数。这个是否正确并没有在问题中明确说明。 - Anders Abel

我喜欢在for循环之前测试前两个元素。甚至可以为两个元素的数组设置保护条件...并完全避免循环。 - Stan Graves

@Anders：没错。对于像{1,2,3,3}这样的输入，second_max的定义可能会有所不同。它可以只是second_max，也可以是与max不同的second_max。我选择了第一种情况，因为它很有道理（至少对我来说），而且这也是标准库std::nth_element所做的。 - codaddict

一个小优化，你可以在循环中先将当前数组元素与second_max比较，如果通过了再与max比较。代码如下： if (arr[i] > second_max) { if (arr[i] > max) { second_max = max; max = arr[i]; } else if (arr[i] != max) { second_max = arr[i]; } }如果数组中没有重复数字，这样做可以保证max和second_max的值总是不同的。 - abhinav

Answer 2

最简单的解决方法是使用std::nth_element。

- avakar

---

好的，请说明 std::nth_element 函数的实现原理。 - Svante

请参见http://en.wikipedia.org/wiki/Selection_algorithm和https://dev59.com/D3E95IYBdhLWcg3wPrkI。 - avakar

删除了我的回答，因为它几乎是重复的。 - Robert Davis

根据选择枢轴的方式不同，最坏情况下的时间复杂度可能为O(N^2)。而具有O(N)保证的一趟算法虽然不能扩展，但对于这个特定问题来说更好。 - polygenelubricants

当数组中存在重复项时，它是否能正常工作？ - Brahim

Answer 3

您需要进行第二次测试：

 for(int i=0;i<5;i++){  
   if(arr[i]>max){  
     second_max=max;  
     max=arr[i];            
   }
   else if (arr[i] > second_max && arr[i] != max){
     second_max = arr[i];
   }
 }

- Anders Abel

---

在第二个测试中，请确保 arr[i] != max；否则，你的 max 和 second_max 可能会相同，这可能会根据你希望的工作方式造成问题。 - ty.

@TopCoder：如果最大值出现两次，应该采取什么样的正确行为？我认为问题中没有明确说明。 - Anders Abel

你可以将第一个测试改为“arr[i]>=max”，并从第二个测试中删除“arr[i] != max”。这将允许max和second_max等于相同的值，但仅当该值在数组中重复时。根据问题的具体情况，这可能是一个有效的答案。 - Stan Graves

Answer 4

请看下面内容：

std::pair<int, int> GetTwoBiggestNumbers(const std::vector<int>& array)
{
    std::pair<int, int> biggest;
    biggest.first = std::max(array[0], array[1]);  // Biggest of the first two.
    biggest.second = std::min(array[0], array[1]); // Smallest of the first two.

    // Continue with the third.
    for(std::vector<int>::const_iterator it = array.begin() + 2;
        it != array.end();
        ++it)
    {
        if(*it > biggest.first)
        {
            biggest.second = biggest.first;
            biggest.first = *it;
        }
        else if(*it > biggest.second)
        {
            biggest.second = *it;
        }
    }

    return biggest;
}

- Johann Gerell

---

奇怪的 std::for_each 用法。 - pmr

@pmr：奇怪的用法 - 以什么方式？ - Johann Gerell

@Johann：std::for_each()不能用作循环语句——它是一个函数。尝试编译你的代码，看看所有那些错误飞过去。你可能想要写的是for。*(顺便说一句：即使有一个for_each语句，++it也会违背意图)* - Georg Fritzsche

@gf：哎呀，C++的日子太久远了……- 已修复。 - Johann Gerell

@Johann：正如gf所说，你使用std::for_each是错误的。你甚至不能将for语句中的块定义为函数对象，因为它依赖于外部的值。不过这只是一个小缺陷。只需将std::for_each更改为for即可。 - pmr

Answer 5

您的原始代码没问题，您只需要初始化max和second_max变量。使用数组中的前两个元素。

- Hans Passant

Answer 6

请检查这个解决方案。

max1 = a[0];
max2 = a[1];

for (i = 1; i < n; i++)
{
    if (max1 < a[i])
    {
        max2 = max1;
        max1 = a[i];
    }

    if (max2 == max1) max2 = a[i + 1];

    if (max2 == a[n])
    {
        printf("All numbers are the same no second max.\n");
        return 0;
    }

    if (max2 < a[i] && max1 != a[i]) max2 = a[i];
}

- mitta

---

如果a [0] = a [1] = max，会发生什么？我认为那时会有问题。 - Origin

Answer 7

Quickselect 是解决这个问题的最佳方法。该链接提供了伪代码，因此我将仅解释整体算法：

QuickSelect for kth largest number:
    Select a pivot element
    Split array around pivot
    If (k < new pivot index)
       perform quickselect on left hand sub array
     else if (k > new pivot index)
       perform quickselect on right hand sub array (make sure to offset k by size of lefthand array + 1)
     else
       return pivot

这显然是基于经典的快速排序算法。

按照这个算法，每次总是选择零元素作为枢轴：

select 4th largest number:
1) array = {1, 3, 2, 7, 11, 0, -4}
partition with 1 as pivot
{0, -4, _1_, 3, 2, 7, 11}
4 > 2 (new pivot index) so...

2) Select 1st (4 - 3) largest number from right sub array
array = {3, 2, 7, 11}
partition with 3 as pivot
{2, _3_, 7, 11}
1 < 2 (new pivot index) so...

3) select 1st largest number from left sub array
array = {2}

4) Done, 4th largest number is 2

这将使你的数组在之后处于未定义的顺序，如果这是一个问题，那就由你决定。

- Martin

Answer 8

步骤1. 决定前两个数字。
步骤2. 循环遍历剩余的数字。
步骤3. 保持最新的最大值和第二大值。
步骤4. 在更新第二大值时，要注意不要使最大值和第二大值相等。

已测试过排序输入（升序和降序）、随机输入、有重复输入，均可正常工作。

#include <iostream>
#define MAX 50
int GetSecondMaximum(int* data, unsigned int size)
{
    int max, secmax;
    // Decide on first two numbers
    if (data[0] > data[1])
    {
        max = data[0];
        secmax = data[1];
    }
    else
    {
        secmax = data[0];
        max = data[1];
    }
    // Loop through remaining numbers
    for (unsigned int i = 2; i < size; ++i)
    {
        if (data[i] > max)
        {
            secmax = max;
            max = data[i];
        }
        else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/)
            secmax = data[i];
    }
    return secmax;
}
int main()
{
    int data[MAX];
    // Fill with random integers
    for (unsigned int i = 0; i < MAX; ++i)
    {
        data[i] = rand() % MAX;
        std::cout << "[" << data[i] << "] "; // Display input
    }
    std::cout << std::endl << std::endl;
    // Find second maximum
    int nSecondMax = GetSecondMaximum(data, MAX);
    // Display output
    std::cout << "Second Maximum = " << nSecondMax << std::endl;
    // Wait for user input
    std::cin.get();
    return 0;
}

- Rajendra Uppal

Answer 9

解决这个问题的另一种方法是使用元素之间的比较。例如，

a[10] = {1,2,3,4,5,6,7,8,9,10}

比较1和2，找出最大值为2，第二大的数为1。

现在比较3和4，并将它们中的最大值与max进行比较。

if element > max
     second max = max
     element = max
else if element > second max
     second max = element

这样做的好处是，你只需要进行两次比较就可以消除两个数字。

如果你对此有任何理解上的问题，请告诉我。

- Boolean

---

打字错误，你需要 max = element。 - Karoly Horvath

Answer 10

#include <iostream>
using namespace std;

int main() {

   int  max = 0;
    int sec_Max = 0;

    int array[] = {81,70,6,78,54,77,7,78};

    int loopcount = sizeof(array)/sizeof(int);

    for(int i = 0 ; i < loopcount ; ++i)
    {

        if(array[i]>max)
        {
            sec_Max = max;
            max = array[i];
        }

        if(array[i] > sec_Max && array[i] < max)
        {
            sec_Max = array[i];
        }
    }

    cout<<"Max:" << max << " Second Max: "<<sec_Max<<endl;

    return 0;
}

- Bunny

---

这个问题在多年前就已经有了详细的回答，而且你的问题并没有添加任何新内容。此外，除了你的代码之外，没有其他评论说明你做了什么 OP 没有做过的。 - coyotte508