找出数组中最大值次大值的一次遍历方法(C++)

写在前面

昨天做了一道LeetCode题(747. 至少是其他数字两倍的最大数 - 力扣（LeetCode） (leetcode-cn.com)), 大致意思是找出数组中的最大值和次大值并返回最大值索引, 如果最大值不小于次大值的2倍, 我因为习惯使用Python, 直接调用库函数就出来了(排序, 判断), 但是这样会花费很长时间, 正好看题解有提到一次遍历的方法, 就在这里总结一下, 用C++重写一遍, 也算巩固巩固C++语法了.

代码与解读

#include <iostream>
#include <vector>

using namespace std;

int test1(vector<int> v)
{
    // 这里设m1为最大值, m2为次大值, idx为最大值对应的数组下标
    // 由于题目中nums中元素为自然数, 所以只需取-1即可
    int m1 = -1, m2 = -1, idx = 0;
    // 对数组中元素进行遍历
    for (int i = 0; i < v.size(); ++i)
    {
        // 如果当前数组元素大于m1, 执行交换
        if (v[i] > m1)
        {
            m2 = m1;
            m1 = v[i];
            idx = i;
        } 
        // 如果当前数组元素在m1和m2之间, 记录m2的值
        else if (v[i] > m2) {
            m2 = v[i];
        }
    }
    return m1>=m2*2?idx:-1;
}


int main(int argc, char const *argv[])
{
    vector<int> v = {3,2,1,6,7};
    // vector<int> v = {3,2,1,7};
    cout<<test1(v)<<endl;
    return 0;
}

简单推广与总结

我们知道, 寻找最大值的方法是一次遍历, 那么寻找最大值和次大值呢?当然也可以, 上面的题目已经给出了解答, 就是通过交换元素的值来实现的, 那么这个方法是不是可以推广到更多的情况呢?

当然也可以, 下面我们来看如果想寻找数组中的最大值, 次大值和次次大值呢? 将上面的题目稍微更改: 如果最大值大于等于次大值和次次大值的和, 返回最大值的下标, 否则返回-1.

int test2(vector<int> &v)
{
    int m1 = -1, m2 = -1, m3 = -1, idx = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        if (v[i] > m1)
        {
            m3 = m2;
            m2 = m1;
            m1 = v[i];
            idx = i;
        } else if (v[i] > m2) {
            m3 = m2;
            m2 = v[i];
        } else if (v[i] > m3) {
            m3 = v[i];
        }
    }
    cout<<m1<<m2<<m3;
    return m1>=m2+m3?idx:-1;
}

同样的, 如果想要计算最小值和次小值, 也可以通过动态改变值的方式一次遍历即可得到(注意这里就得取m1为INT_MAX了). 代码如下

int test3(vector<int> &v)
{
    int m1 = INT_MAX, m2 = INT_MAX, idx = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        if (v[i] < m1)
        {
            m2 = m1;    
            m1 = v[i];
            idx = i;
        } else if (v[i] < m2) {
            m2 = v[i];
        } 
    }
    cout<<m1<<m2;
    return m1<=m2*2?idx:-1;
}

其实只需改变一下符号即可.

我的理解是这种方法有点像链表中用到的双指针, 不断遍历然后修改值, 就能达到想要的结果.