Python 两个数组嵌套循环的优化

Question

在评估中，我得到以下问题：

“有两支队伍，规模为 N，队伍中每个球员的技能值都存储在一个数组中，编写一个算法，计算第一支球队在一轮比赛中获胜的所有次数。找出第一支球队是否获胜赢得一轮比赛后，有必要比较两支球队之间的球员对，考虑到比较可以以

(0<=i<j<n)

的形式进行。本质上，当且仅当

group1[i]+group1[j ] > group2[i]+group2[j]

则一队获胜”

我想出了一个 O(n^2) 时间复杂度的解决方案，如下：

def countWins(group1, group2):
    n = len(group1)
    wins = 0
    for i in range(n):
        for j in range(i+1, n):
            if group1[i] + group1[j] > group2[i] + group2[j]:
                wins += 1
    return wins

尽管算法很简单，我还是简单解释一下：

通过最外层循环收集该对的第一个元素，而由于最内层的循环，该对的第二个元素被收集，而不考虑那些位于“i”之前或等于“i”的位置。

对于每个检测到的对，如果满足跟踪条件，获胜计数器就会递增。

我想降低算法的复杂性是使用另一种数据结构，但我仍然必须遍历这两个数组，这将使得使用除我所拥有的结构之外的任何结构不可避免地降低效率（我可能错了）。

我还认为对数组进行排序可能有助于获得更好的解决方案，但没有想到任何有用的东西。

Answer 1

让我们改变问题，而不是寻找位置

group1[i] + group1[j] > group2[i] + group2[j]

我们可以将右侧移到左侧

(group1[i] - group2[i])+ (group1[j] - group2[j]) >  0

然后如果我们只减去两个数组

differences = group1 - group2 # assume this works
differences[i] + differences[j] > 0

现在的问题是找到总和大于0的对(i,j)，这个问题是众所周知的，我可能只是从极客那里窃取它的解决方案，因为极客数量大于0 并将其转换为Python，如下所示：

import bisect

def countWins(group1, group2):
    wins = 0
    differences = [x-y for x,y in zip(group1,group2)]
    differences.sort()
    first_index = 0
    second_index = len(differences) - 1
    total_len = len(differences)
    a = differences
    n = len(differences)
    # Loop to iterate through the array
    for i in range(n): 
 
        # Ignore if the value is negative
        if (a[i] <= 0):
            continue
 
        # Finding the index using lower_bound
        j = bisect.bisect_left(a, -a[i] + 1);
 
        # Finding the number of pairs between
        # two indices i and j
        wins += i - j;
    
    return wins
def main():
    arr1 = [1,3,4,6]
    arr2 = [0,1,4,7]
    print(countWins(arr1,arr2))

main()

4