1〜50号运动员按顺序排成一排。教练下令：“单数运动员出列！”剰下的运动员重新排队编号。教练又下令：“单数运动员出列！ ”如此下去，最后只剰下一个人，他是几号运动员？如果教练下的令是“双数运动员出列！”最后剰下的又是谁？
题解：## 思路
如果是双数出列，那么由于1号从来都没有动过，因此剩下的是1号。
如果是单数数列，每次剩下的人的编号分别是$2^N$,其中N为轮数。因此最后剩下的人的编号为$2^N$,而由于每次人数减少一半，因此总的轮数为`Math.log2(n) >>> 0`，其中 >>> 0 为向下取整，为的是处理总人数为奇数的情况。 这题可以扩展到一般，给定任意人数，可以求出最后剩下的号码。
## 代码
```js
function test(n) {
return Math.pow(2, Math.log2(n) >>> 0);
}
```
时间和空复杂度实际上取决于 log2 和 pow的实现，而对于不同的CPU其时间复杂度不尽相同，以下是大致的复杂度。 pow的时间和空间复杂度近似$(1)$，log2的时间复杂度近似为$log log n$,空间复杂度近似为$O(log n)$
***复杂度分析***
- 时间复杂度：$O(log log n)$
- 空间复杂度：$O(log n)$
更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经30K star啦。
大家也可以关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解
LeetCode题解 链表的冒泡排序可以使用 https://leetcode-cn.com/problems/sort-list/ 进行测试。 但是本题的要求不是时间复杂度$O(N*logN)$，而是要求使用冒泡排序算法题解：## Python Solution```pythonclass Solution: def sortList(self, head: ListNode) -> …
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924
LeetCode题解烧绳子烧一根不均匀的绳要用一个小时，如果要准确判断一个小时十五分钟，至少需要几根绳子？注意：- 每一根绳子虽然都可以烧一个小时，但均匀程度都不一样题解：三根1. 第一根点燃一头的同时，第二根两头同时点燃。2. 点燃两头的绳子燃尽时，同时点燃第一根绳子的另一头 并开始计时3. 等第一根绳子燃尽 再点燃第三根绳子的一头4. 燃尽 一小时十五分钟
LeetCode题解堆排序和快速排序堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。 那么两者谁更快呢？ 为什么？题解：快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧