如何在较短的时间内将列表中的每个元素添加到同一列表的另一个元素中？

Question

Input : l1 = [1,2,3,4,5,6]
Output :     [7, 8, 9, 10, 11, 11]

若要查找列表中每对元素的最大和，请执行以下操作。通常，我必须将列表中的每个元素添加到另一个元素中(而不是自己)。下面是我尝试过的代码。我知道这是(n^2)的复杂性

有没有更好的方法来降低复杂性(可以是时间也可以是空间)？

有什么更好的方法(可能是使用某些模块，或者只使用单个for循环)？

list l1不需要在sorted中。

l2=[]
l3=[]
for i in range(len(l1)):
   for j in range(len(l1)):
      if i!=j:
         l2.append(l1[i]+l1[j])
   l3.append(max(l2))
   l2.clear()



print(l3)
[7, 8, 9, 10, 11, 11]

更新：在hackerrank中提交了该解决方案，但很少失败。失败的原因是TimeLimitExceed (TLE)。我想，这是由于大量的失败。

**Constraints:**
n = size_of_list

1<= n <= 4*10^4
1<= l1[i] <= 1024
1<= i <= n
1<= j <= n
j != i

是因为time-complexity，无法在上面的代码段中处理这些场景吗？

Answer 1

首先，我们可以根据自己的优势使用排序。Python排序方法sorted在O(n log n) time中操作。(参见这个问题：What is the complexity of this python sort method?)

一旦我们的数字被排序，最大和是微不足道的。数字的最大值仅仅是添加到排序列表中的最后一个元素的数字，或者，如果数字是最大元素，则是第二个到最后一个元素。重写我们可以获得的代码：

l3 = []
l1 = sorted(l1)

for i in range(len(l1)):
    if i + 1 == len(l1):
        l3.append(l1[i] + l1[i - 1])
    else:
        l3.append(l1[i] + l1[-1])

print(l3)

我希望这能帮到你。如果我误解了你的问题，请告诉我。

Answer 2

你可以这样做：

l1 = [1,2,3,4,5,6]
l2=[]
for i in range(len(l1)):
    for j in range(i+1,len(l1)):
            l2.append(l1[i]+l1[j])
l3=set(l2)
l2=list(l3)
print(l2)

产出：

[3, 4, 5, 6, 7, 8, 9, 10, 11]

在处理前对列表进行排序也有帮助。如果我犯了什么错误，请告诉我。

Answer 3

您可以在O(n)中这样做。

其基本思想是获取列表中最大元素和第二个最大元素的索引。然后，对于列表中的每个元素，如果元素不是max_element，则追加元素+ max_element、。否则，追加max_element + second_max_element。

我使用get_first_second_max_index来获取maximum元素和第二个maximum元素的索引，因为列表中可能有相同的元素。

代码应该如下所示：

def get_first_second_max_index(nums):
    if len(nums) < 2:
        return None, None

    first_max_index = 0 if nums[0] > nums[1] else 1
    second_max_index = 0 if nums[0] <= nums[1] else 1

    for index in range(2, len(nums)):
        if nums[index] > nums[first_max_index]:
            first_max_index, second_max_index = index, first_max_index
        elif nums[index] > nums[second_max_index]:
            second_max_index = index

    return (first_max_index, second_max_index)


def max_sum_pair(nums):
    res = []
    if len(nums) >= 2:
        first_max_index, second_max_index = get_first_second_max_index(nums)

        for index in range(len(nums)):
            if index == first_max_index:
                res.append(nums[index] + nums[second_max_index])
            else:
                res.append(nums[index] + nums[first_max_index])

    return res

nums = [1,2,3,4,5,6]
res = max_sum_pair(nums)
print(res)