You are given an integer n, the number of teams in a tournament that has strange rules:
If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.
Return the number of matches played in the tournament until a winner is decided.
Example 1:
Input: n = 7
Output: 6
Explanation: Details of the tournament:
- 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 3 + 2 + 1 = 6.
Example 2:
Input: n = 14
Output: 13
Explanation: Details of the tournament:
- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 7 + 3 + 2 + 1 = 13.
Constraints:
1 <= n <= 200
比赛中的配对次数。
给你一个整数 n ,表示比赛中的队伍数。比赛遵循一种独特的赛制:
如果当前队伍数是 偶数 ,那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛,且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ,那么将会随机轮空并晋级一支队伍,其余的队伍配对。总共进行 (n - 1) / 2 场比赛,且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数,直到决出获胜队伍为止。
思路
当队伍个数 n 不等于 1 的时候,就需要一直配对来比较到底谁是最后的胜者。题目规定了当队伍个数为偶数的时候,就两两配对看谁是胜者;当队伍个数为偶数的时候,可以随机挑出一个胜者,让剩下的人再两两配对看谁是胜者,所以无论队伍个数是奇数还是偶数,配对次数永远都是当前队伍个数 / 2
。
复杂度
时间O(n/2)
空间O(1)
代码
Java实现
class Solution {
public int numberOfMatches(int n) {
int count = 0;
while (n != 1) {
count += n / 2;
if (n % 2 == 1) {
n = n / 2 + 1;
} else {
n /= 2;
}
}
return count;
}
}
- Tournament LeetCode Matches Count 1688tournament leetcode matches count unreachable undirected leetcode count occurrence leetcode common count leetcode target count pairs communicate leetcode servers count leetcode number count pairs leetcode strings ranges count leetcode average subtree count matches quot standard matches binary