1688-比赛中的配对次数

给你一个整数 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

方法一：模拟

思路与算法

我们直接模拟题目描述中的赛制即可。

代码

[sol1-C++]

class Solution {
public:
    int numberOfMatches(int n) {
        int ans = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                ans += n / 2;
                n /= 2;
            }
            else {
                ans += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        return ans;
    }
};

[sol1-Java]

class Solution {
    public int numberOfMatches(int n) {
        int ans = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                ans += n / 2;
                n /= 2;
            } else {
                ans += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        return ans;
    }
}

[sol1-C#]

public class Solution {
    public int NumberOfMatches(int n) {
        int ans = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                ans += n / 2;
                n /= 2;
            } else {
                ans += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        return ans;
    }
}

[sol1-Python3]

class Solution:
    def numberOfMatches(self, n: int) -> int:
        ans = 0
        while n > 1:
            if n % 2 == 0:
                ans += n // 2
                n //= 2
            else:
                ans += (n - 1) // 2
                n = (n - 1) // 2 + 1
        return ans

[sol1-Golang]

func numberOfMatches(n int) int {
	ans := 0
	for n > 1 {
		if n%2 == 0 {
			ans += n / 2
			n /= 2
		} else {
			ans += (n - 1) / 2
			n = (n-1)/2 + 1
		}
	}
	return ans
}

[sol1-C]

int numberOfMatches(int n){
    int ans = 0;
    while (n > 1) {
        if (n % 2 == 0) {
            ans += n / 2;
            n /= 2;
        } else {
            ans += (n - 1) / 2;
            n = (n - 1) / 2 + 1;
        }
    }
    return ans;
}

[sol1-JavaScript]

var numberOfMatches = function(n) {
    let ans = 0;
    while (n > 1) {
        if (n % 2 === 0) {
            ans += Math.floor(n / 2);
            n /= 2;
        } else {
            ans += Math.floor((n - 1) / 2);
            n = Math.floor((n - 1) / 2) + 1;
        }
    }
    return ans;
};

复杂度分析

• 时间复杂度：O(\log n)。每一轮后会有一半（向下取整）数量的队伍无法晋级，因此轮数为 O(\log n)。每一轮需要 O(1) 的时间进行计算。

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

方法二：数学

思路与算法

在每一场比赛中，输的队伍无法晋级，且不会再参加后续的比赛。由于最后只决出一个获胜队伍，因此就有 n-1 个无法晋级的队伍，也就是会有 n-1 场比赛。

代码

[sol2-C++]

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

[sol2-Java]

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

[sol2-C#]

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

[sol2-Python3]

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

[sol2-Golang]

func numberOfMatches(n int) int {
	return n - 1
}

[sol2-C]

int numberOfMatches(int n){
    return n - 1;
}

[sol2-JavaScript]

var numberOfMatches = function(n) {
    return n - 1
};

复杂度分析

• 时间复杂度：O(1)。

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