给定一组比赛结果，我怎样才能在 O(n) 时间内得到最多输 10 场的所有球队？

Question

我正在尝试编写伪代码来解决以下问题：

输入：一场篮球比赛中的 n 支球队。每支球队 Ti、Tj 比赛，他们的 win/loss 记录在矩阵 A
中（对于 i < j，如果 Ti 击败 Tj，A[i, j] = 1）

如果一个团队输掉的次数不超过 10 次，他们将获得一枚奖牌。

输出：所有获得奖牌的团队。在 O(n) 时间内查找。

到目前为止，这是我的伪代码。伪代码现在就足够了，但我认为这不能正常工作，也不能在线性时间内运行。

//input: matrix A of win/losses
//output: list of teams with medals
set S to an array of length n, with value 0 for all indices //keeps track of number of losses
for each team:
    for each game played in the team's row in M:
        if the team won:
            increment the opponent’s number of losses in the opponent’s index of S
        else:
            increment the team's number of losses in team's index of S
            if at any point a value in the array S reaches 11, remove that team from the list of teams we consider //so basically ignore all the games they play from hereon out
    end for loop
end for loop
take this new potential list of teams with medals
iterate through each team's row in M, counting losses       //to check if they lost against any of the teams we removed from the previous for loop
if losses > 10, remove the team from list
return final list

Answer 1

在 O(n) 中执行此操作是一个非常有趣的问题。

有可能，因为我们只对输球次数不超过10次的球队感兴趣。

但即使有这个约束，找到一个 O(n) 算法并证明它是 O(n) 也不是直截了当的。

首先，这里有一些东西 不起作用 ：取矩阵的每一行（代表一个团队），一个一个地查看它的元素，一旦我们遇到 11 场失利，打破这支球队的循环，跳过其余的结果。

这仍然是 O(n^2) —— 例如考虑较低索引的团队总是输给较高索引的团队的情况。结果矩阵将是下三角矩阵（在对角线下方只有 1，在对角线上方只有 0）。

在这种情况下，所提到的算法需要调查对角线下方的所有元素（因为它们都是 1，在行的开头，导致在达到 11 损失时没有进展，我们在此处打破循环).所以这里至少研究了 (n^2 - n) / 2 个元素，因此这种方法不在 O(n) 中。

你提到的伪代码是比这个更好的尝试，但它也不在 O(n) 内。使用相同的反例可以看出这一点。（此外，伪代码是不正确的，因为它有时会重复计算损失，但这可以通过使用一个额外的数组来解决，该数组将指示每支球队最后处理的比赛）。

现在我将描述一个 似乎可行 的想法。这似乎是在正确的轨道上，但有一些我无法解决的复杂问题。

为了在 O(n) 中，我们需要仔细选择要查看其结果的匹配项。

我们将维护 11 组团队：L0、L1、...、L11。

L0 是一组我们目前不知道有任何损失的球队。最初，所有团队都在这个集合中。
L1 是我们目前知道他们输了 1 场的一组球队。
...
L10 是我们目前知道他们输了 10 场的一组球队。
L11 是我们目前知道他们输了 10 场以上的球队的集合。

最初，L0 将包含所有团队，其他集合为空。

现在，将 L0 中的团队配对。调查他们的比赛，将失败者移至 L1。这将涉及大约 n/2 个操作，我们将在 L0 中留下大约 n/2 个团队，在 L1 中留下 n/2 个团队（"about n/2"，因为 n 可能是奇数，其中如果一个团队现在不会配对）。对留在 L0 中的 n/2 队重复该过程，再次移动 L1 中的失败者。这将需要 n/2/2 = n/4 操作。如此继续下去，直到L0只剩下一支队伍。这将需要一些 n/2 + n/4 + ... + 1 操作，这是在 O(n) 中。

我们现在只剩下集合 L0 的一个候选者，这已经足够了（我们可以在 O(n) 中调查它是否确实有低于 10 的损失）。

显然我们可以继续这样并向 L2 移动，现在在 L1 中的团队，在 O(n) 中，然后在 L3 中，依此类推，直到大多数团队被推入 L11（我们不这样做）不再关心他们了）。但是将球队赶出 L1 并不像 L0 那样简单——我们现在需要注意我们看的是哪些比赛，因为其中一些可能已经在之前的阶段进行过调查。

Answer 2

基于 qwertyman 的方法，我们可以在 O(n) 中解决这个问题，如下所示：

跟踪每支球队的失利次数
跟踪剩余的团队（即损失 10 次或更少的团队 - 我们通过保留索引数组和交换元素以进行恒定时间移除来做到这一点）
从剩余的队伍中循环所有可能的比赛
- 增加失败队伍的失败次数
- 如果损失计数大于 10，则将该团队从剩余团队中移除
- 注意：此循环似乎需要 O(n²)，但剩余团队的数量减少得足够快，因此只需要 O(n)。
  您可以从我们每次迭代增加损失计数这一事实中看出这一点，并且损失计数的最大总和为 11*n（因为一旦损失计数为 11，我们将其从考虑中删除并且不再增加它更多），因此这个循环最多运行s 11*n = O(n) 次。
现在最多剩下21支球队。
这是如果我们不知道剩余的团队对任何已被移除的团队有任何损失（很容易看出这是最好的情况），然后每个剩余的团队都赢了其他 20 个剩余团队中的 10 个。 22支球队是不可能的，因为每支球队需要至少赢11/21场比赛才能保持10场或更少的输球，导致胜多于负，考虑到每场比赛有1胜1负，这是不可能的。
对于剩下的每支球队，我们只需运行计算该球队的所有比赛并计算输球次数（21 轮 O(n) = O(n)）并输出输了10场或更少的球队。

Java-like 代码：（为了可读性略微修改了工作版本）

// returns true if i beat j or false if j beat i
boolean beat(int i, int j);
// return the loser in the game between i and j
int loser(int i, int j);
// swaps i with the last element in indices and decreases index count, takes O(1)
void removeIndex(int i);

// x = indices[y] corresponds to a remaining team x
int[] indices = new int[n];
// number of elements in indices, decreased in removeIndex
int indicesCount = n;

// initialise our array of indices
for (int i = 0; i < n; i++)
    indices[i] = i;

// initialise our array of losses
losses = new int[n];

// loop over all possible match-ups and eliminate (some) teams with > 10 losses
for (int a = 0; a < indicesCount; )
{
    for (int b = a+1; losses[indices[a]] <= 10 && b < indicesCount; )
    {
        losses[loser(indices[a], indices[b])]++;

        if (losses[indices[b]] > 10)
            removeIndex(b);
        else
            b++;
    }
    if (losses[indices[a]] > 10)
        removeIndex(a);
    else
        a++;
}

// find teams with <= 10 losses
for (int i = 0; i < indicesCount; i++)
{
    int lossCount = 0;
    for (int j = 0; j < n; j++)
        if (indices[i] == j)
            continue;
        else if (beat(j, indices[i]))
            lossCount++;
    if (lossCount <= 10)
        // output indices[i]
}

Live demo.

给定一组比赛结果，我怎样才能在 O(n) 时间内得到最多输 10 场的所有球队？

Given a set of match results, how can I get all teams with at most 10 losses in O(n) time?

algorithm

performance

pseudocode