讨论/技术交流/数组中任意两个数相加的最大值,时间复杂度是O(n)/
数组中任意两个数相加的最大值,时间复杂度是O(n)

数组中任意两个数相加的最大值,时间复杂度是O(n).

共 9 个回复

上面说的很有道理

1

各位大哥,我想学Python,可不知道怎么学,这个软件我才下的,现在是完全零基础,算法题根本看不懂,我该怎么学呢?求指点

1.遍历一次拿到最大值,遍历第二次拿最小值
2.直接sort取最后两个值
3.遍历一遍插入最小堆取最后两个

感谢提醒,这里没有考虑到数组中的重复元素,疏忽了。已修改。

试下这组数据:

[100,100]

Python3 伪代码举个例子:

def largestTwoSums(array):
    assert(len(array))>=2

    max1=max2=-2147483648

    for i in array:
        if max1>=i>=max2:
            max2=i
            continue

        if i>max1:
            max1,max2=i,max1

    return max1+max2

这就相当于topk问题,用快选可以做到o(n)

最大 和 次大 有没有好方法 直接比较两次么

遍历一次记录最大和次大的两个数,求和即得。