LeetCode 1688. 比赛中的配对次数
发布时间:2023-02-09 04:22:12 226
相关标签:
给你一个整数 n
,表示比赛中的队伍数。比赛遵循一种独特的赛制:
- 如果当前队伍数是 偶数 ,那么每支队伍都会与另一支队伍配对。总共进行
n / 2
场比赛,且产生 n / 2
支队伍进入下一轮。 - 如果当前队伍数为 奇数 ,那么将会随机轮空并晋级一支队伍,其余的队伍配对。总共进行
(n - 1) / 2
场比赛,且产生 (n - 1) / 2 + 1
支队伍进入下一轮。
返回在比赛中进行的配对次数,直到决出获胜队伍为止。
示例 1:
示例 2:
提示:
-
1 <= n <= 200
二、方法一
模拟
复杂度分析
- 时间复杂度:O(logn)。每一轮后会有一半(向下取整)数量的队伍无法晋级,因此轮数为O(logn)。每一轮需要 O(1)的时间进行计算。
- 空间复杂度:O(1)。
三、方法二
由于最后只决出一个获胜队伍,因此就有 n-1个无法晋级的队伍,也就是会有 n-1 场比赛。
复杂度分析
- 时间复杂度:O(1)。
- 空间复杂度:O(1)。
文章来源: https://blog.51cto.com/u_15949251/6029142
特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报