创建一个更有效的算法来获取 python 中元素与列表中另一个元素的第三大差异

Question

这是我大学的一个编程问题活动。我将修改问题以避免抄袭。

假设一个小组中有 n 个人。对于每个人，我们从 0 到 n−1 进行编号。每个人都有一个列表中展示的个性值。例如，列表 [2, 3, 4, 6] 显示人物 0 的个性值为 2，人物 1 的个性值为 3，人物 2 的个性值为 3，人物 3 的个性值为 3。共 6 个。

我们将一个人与另一个人的享受定义为 |pi - pj|其中 i 和 j 是 p 的下标，是列表的索引。

为了更好地说明，让我们再次使用列表作为示例。

• 人 0 与人 1 感受到的享受是 |2 - 3|这是 1。
• 人 0 与人 2 感受到的享受是 |2 - 4|是 2，
• 人 0 与人 3 感受到的享受是 |2 - 6|是 4，对于第 1 个人来说也是如此，依此类推。

我想创建一个函数，返回一个人对群体中另一个人的第三大享受。因此，对于上面的列表，我应该得到 [1, 1, 1, 2] 的输出。保证一群朋友大于4个。性格也可以是负的。

代码：

def third_enjoyment(p: list[int]) -> list[int]:
    n: int = len(p)
    e: list[int] = []

    for i in range(n):
        enjoyment = [abs(p[i] - p[j]) for j in range(n) if j != i]
        enjoyment.sort()
        third_enjoyment = enjoyment[-3]
        e.append(third_enjoyment)

    return e

这是我对这个问题的解决方案。我不确定时间，但我认为这个解决方案的时间复杂度为 O(n^2) （不太确定，因为我们还没有讨论时间复杂度是如何工作的），这很糟糕，因为当我尝试将代码提交到判断是否超过时限。我想知道一种比这种暴力解决方案更快的更好的方法来解决这个问题。

Answer 1

我认为优化算法的一种方法是通过将列表中的每个项目存储在

(<p value>, <original index>)

的元组结构中来对个性值列表进行排序，同时保留其原始索引

sp = sorted([(p[i], i) for i in range(len(p))])

对于排序列表中索引为

i

的每个项目，您知道与其值的最大差异位于排序列表中该项目的左侧或右侧。您可以使用两个指针

l

，

r

分别代表排序列表中项目左侧和右侧的索引，并将其与项目值的差异进行比较（

abs(value - sp[l][0]) >= abs(sp[i][0] - sp[r][0])

）。最初，

l

和

r

分别用

0

和

n-1

初始化，代表排序列表中项目

i

的最左端和最右端。如果左侧的差异比右侧大，则您知道左侧的差异最大，因此您将

l

索引增加 1，更接近项目的索引，以找到第二大差异。如果右侧的差异比左侧大，则您知道右侧的差异最大，因此您将

r

索引减少 1，更接近 来找到第二大差异。您可以继续执行此操作 3 次以获得第三大差异，并将结果应用于给定原始索引处的数组。需要注意的一件事是，

l

边界只能是

[0, i - 1]

，而

r

边界只能是

[i + 1, n - 1]

，因此如果

l

或

r

首先触及它们的边界，则只有另一个指针有权利结果，可以不断增加/减少，直到达到总迭代次数

def third_enjoyment(p: list[int]) -> list[int]:
    n: int = len(p)
    e: list[int] = [-1] * n
    
    # sorted data structure of p in the format (<value>, <original index>)
    # O(nlog(n))
    sp = sorted([(p[i], i) for i in range(len(p))])

    # O(n)
    for i in range(len(sp)):
        value, original_index = sp[i]

        # left, right pointer from sorted list
        l, r = 0, n - 1

        for itt in range(3):
            if l < i:
                # left pointer still within bound
                abs_l = abs(value - sp[l][0])

                if r > i:
                    # right pointer still within bound
                    abs_r = abs(value - sp[r][0])
                    if abs_l >= abs_r:
                        e[original_index] = abs_l
                        l += 1
                    else:
                        e[original_index] = abs_r
                        r -= 1
                else:
                    # right pointer out of bound
                    e[original_index] = abs_l
                    l += 1
            elif r > i:
                # left pointer out of bound, right pointer within bound
                e[original_index] = abs(value - sp[r][0])
                r -= 1
            else:
                # both left and right pointers out bound
                break
    return e

p = [2, 3, 4, 6]
print(third_enjoyment(p))