题目描述(题目来源于LeetCode)

给你一个整数 n ，表示比赛中的队伍数。比赛遵循一种独特的赛制：

  • 如果当前队伍数是 偶数 ，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
  • 如果当前队伍数为 奇数 ，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
    返回在比赛中进行的配对次数，直到决出获胜队伍为止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:

    def numberOfMatches(self, n: int) -> int:

        x=0

        while n!=1:

            if n%2==0:

                x+=n//2

                n=n//2

            else:

                x+=(n-1)//2

                n=(n-1)//2+1

        return x

代码分析

算法思路

代码采用迭代方法模拟比赛过程：

  1. 初始化配对次数 x 为 0

  2. 当队伍数 n 大于 1 时循环：

    • 如果 n 是偶数：配对次数增加 n/2，下一轮队伍数为 n/2

    • 如果 n 是奇数：配对次数增加 (n-1)/2，下一轮队伍数为 (n-1)/2 + 1

  3. 当队伍数减少到 1 时，返回总配对次数

时间复杂度分析

  • 时间复杂度：O(logN)O(log N)

    • 每次迭代队伍数至少减半

    • 最坏情况下需要 O(log N) 次迭代

  • 空间复杂度：O(1)O(1)

    • 只使用了常数级别的额外空间

代码正确性

代码逻辑清晰，正确处理了奇偶两种情况：

  • 偶数情况：x += n//2 和 n = n//2

  • 奇数情况：x += (n-1)//2 和 n = (n-1)//2 + 1

优化建议

实际上，这个问题有一个数学上的封闭解：配对次数总是等于 n-1，因为每场比赛淘汰一支队伍，最终只剩一支冠军队伍。

可以直接简化为：

1
2
3

def numberOfMatches(self, n: int) -> int:
    return n - 1