Easy

题目描述

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

  • 如果当前队伍数是偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，共有 n / 2 支队伍晋级到下一轮。
  • 如果当前队伍数为奇数，那么将会随机选出一支队伍晋级，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，共有 (n - 1) / 2 + 1 支队伍晋级到下一轮。

返回在比赛中进行的配对总数，直到决出获胜者为止。

示例 1：

输入：n = 7
输出：6
解释：比赛详情：
- 第 1 轮：队伍数 = 7 ，比赛场数 = 3 ，4 支队伍晋级。
- 第 2 轮：队伍数 = 4 ，比赛场数 = 2 ，2 支队伍晋级。
- 第 3 轮：队伍数 = 2 ，比赛场数 = 1 ，决出 1 支获胜队伍。
总比赛场数 = 3 + 2 + 1 = 6

示例 2：

输入：n = 14
输出：13
解释：比赛详情：
- 第 1 轮：队伍数 = 14 ，比赛场数 = 7 ，7 支队伍晋级。
- 第 2 轮：队伍数 = 7 ，比赛场数 = 3 ，4 支队伍晋级。
- 第 3 轮：队伍数 = 4 ，比赛场数 = 2 ，2 支队伍晋级。
- 第 4 轮：队伍数 = 2 ，比赛场数 = 1 ，决出 1 支获胜队伍。
总比赛场数 = 7 + 3 + 2 + 1 = 13

提示：

  • 1 <= n <= 200

解题思路

解题思路

方法一：模拟比赛过程 按照题目描述直接模拟整个锦标赛过程。每一轮根据当前队伍数的奇偶性计算比赛场数和晋级队伍数，累加比赛场数直到只剩一支队伍。

方法二：数学推理（推荐） 通过观察可以发现一个重要规律：每场比赛都会淘汰恰好一支队伍，而最终只能有一支获胜队伍。因此，要从 n 支队伍中淘汰到只剩 1 支队伍，需要淘汰 n-1 支队伍，即需要进行 n-1 场比赛。

这个结论可以通过归纳法证明：

  • 当 n=1 时，不需要比赛，答案为 0 = 1-1
  • 当 n>1 时，无论是奇数还是偶数队伍，每轮比赛后队伍数都会减少，且每场比赛淘汰一支队伍

数学方法时间复杂度更优，代码更简洁，是最佳解法。

代码实现

class Solution {
public:
    int numberOfMatches(int n) {
        return n - 1;
    }
};

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

public class Solution {
    public int NumberOfMatches(int n) {
        return n - 1;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var numberOfMatches = function(n) {
    return n - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
模拟方法O(log n)O(1)
数学推理O(1)O(1)

相关题目