Easy

题目描述

给你一个介于 1 到 100 之间的整数数组 bulbs。

有 100 个编号从 1 到 100 的灯泡。所有灯泡最初都是关闭的。

对于数组 bulbs 中的每个元素 bulbs[i]：

  • 如果第 bulbs[i] 个灯泡当前是关闭的，则将其打开。
  • 否则，将其关闭。

返回最终打开的灯泡编号列表，按升序排列。如果没有灯泡打开，返回空列表。

示例 1：

输入：bulbs = [10,30,20,10]
输出：[20,30]
解释：
- bulbs[0] = 10，第 10 个灯泡当前是关闭的。我们将其打开。
- bulbs[1] = 30，第 30 个灯泡当前是关闭的。我们将其打开。
- bulbs[2] = 20，第 20 个灯泡当前是关闭的。我们将其打开。
- bulbs[3] = 10，第 10 个灯泡当前是打开的。我们将其关闭。
- 最终，第 20 个和第 30 个灯泡是打开的。

示例 2：

输入：bulbs = [100,100]
输出：[]
解释：
- bulbs[0] = 100，第 100 个灯泡当前是关闭的。我们将其打开。
- bulbs[1] = 100，第 100 个灯泡当前是打开的。我们将其关闭。
- 最终，没有灯泡是打开的。

约束条件：

  • 1 <= bulbs.length <= 100
  • 1 <= bulbs[i] <= 100

提示：

  • 按描述进行模拟

解题思路

这是一道简单的模拟题，我们需要跟踪每个灯泡的开关状态。

核心思路： 每次遇到一个灯泡编号，我们就切换它的状态。由于灯泡的状态只有开和关两种，我们可以用异或操作来实现切换。

算法步骤：

  1. 使用一个布尔数组或哈希表记录每个灯泡的状态（初始都是关闭的）
  2. 遍历输入数组，对每个灯泡编号执行切换操作
  3. 最后收集所有打开的灯泡编号，按升序排列返回

优化思路： 我们可以直接使用哈希表来记录每个灯泡被操作的次数。如果操作次数是奇数，说明灯泡最终是打开的；如果是偶数，说明灯泡最终是关闭的。这样可以避免维护布尔数组。

由于题目要求结果按升序排列，我们可以直接遍历 1 到 100 的所有编号，检查哪些灯泡最终是打开的。

代码实现

class Solution {
public:
    vector<int> toggleLightBulbs(vector<int>& bulbs) {
        unordered_map<int, int> count;
        
        // 统计每个灯泡被操作的次数
        for (int bulb : bulbs) {
            count[bulb]++;
        }
        
        vector<int> result;
        // 检查每个可能的灯泡编号（1到100）
        for (int i = 1; i <= 100; i++) {
            // 如果操作次数为奇数，灯泡最终是打开的
            if (count[i] % 2 == 1) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def toggleLightBulbs(self, bulbs: list[int]) -> list[int]:
        count = {}
        
        # 统计每个灯泡被操作的次数
        for bulb in bulbs:
            count[bulb] = count.get(bulb, 0) + 1
        
        result = []
        # 检查每个可能的灯泡编号（1到100）
        for i in range(1, 101):
            # 如果操作次数为奇数，灯泡最终是打开的
            if count.get(i, 0) % 2 == 1:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> ToggleLightBulbs(IList<int> bulbs) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        // 统计每个灯泡被操作的次数
        foreach (int bulb in bulbs) {
            if (count.ContainsKey(bulb)) {
                count[bulb]++;
            } else {
                count[bulb] = 1;
            }
        }
        
        List<int> result = new List<int>();
        // 检查每个可能的灯泡编号（1到100）
        for (int i = 1; i <= 100; i++) {
            // 如果操作次数为奇数，灯泡最终是打开的
            if (count.ContainsKey(i) && count[i] % 2 == 1) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} bulbs
 * @return {number[]}
 */
var toggleLightBulbs = function(bulbs) {
    const state = new Set();
    
    for (const bulb of bulbs) {
        if (state.has(bulb)) {
            state.delete(bulb);
        } else {
            state.add(bulb);
        }
    }
    
    return Array.from(state).sort((a, b) => a - b);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n + 100) = O(n)，其中 n 是 bulbs 数组的长度。需要遍历一次 bulbs 数组统计操作次数，然后遍历 1-100 检查状态
空间复杂度O(k)，其中 k 是不同灯泡编号的数量，最多为 100。哈希表存储每个被操作过的灯泡的计数