Medium
题目描述
有 n 个灯泡，开始时都处于关闭状态。你首先打开所有的灯泡，然后关闭每第二个灯泡。
第三轮，你切换每第三个灯泡（如果关闭则打开，如果打开则关闭）。第 i 轮，你切换每第 i 个灯泡。第 n 轮，你只切换最后一个灯泡。
返回 n 轮后有多少个灯泡亮着。
示例 1：
输入：n = 3
输出：1
解释：
初始时，三个灯泡的状态 [关闭, 关闭, 关闭]。
第一轮后，三个灯泡的状态 [打开, 打开, 打开]。
第二轮后，三个灯泡的状态 [打开, 关闭, 打开]。
第三轮后，三个灯泡的状态 [打开, 关闭, 关闭]。
你应该返回 1，因为只有一个灯泡还亮着。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：1
提示：
0 <= n <= 10^9
解题思路
这道题看似复杂，但实际上有一个非常巧妙的数学规律。
我们来分析每个灯泡被切换的次数。对于第 i 个灯泡（1 ≤ i ≤ n），它会在第 j 轮被切换，当且仅当 j 能整除 i。换句话说，第 i 个灯泡被切换的次数等于 i 的因数个数。
关键观察：一个数的因数通常是成对出现的。例如，12 的因数有 1×12、2×6、3×4，所以因数个数为偶数。但是完全平方数是例外，比如 9 的因数有 1×9、3×3，其中 3×3 只算一个因数，所以完全平方数的因数个数为奇数。
由于灯泡初始状态为关闭，被切换奇数次后会亮着，偶数次后仍然关闭。因此，只有编号为完全平方数的灯泡最终会亮着。
问题转化为：在 1 到 n 中有多少个完全平方数？答案就是 ⌊√n⌋（n 的平方根的整数部分）。
这个解法的时间复杂度为 O(1)，空间复杂度为 O(1)，非常高效。
代码实现
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(n ** 0.5)
public class Solution {
public int BulbSwitch(int n) {
return (int)Math.Sqrt(n);
}
}
/**
* @param {number} n
* @return {number}
*/
var bulbSwitch = function(n) {
return Math.floor(Math.sqrt(n));
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |