2026-06-14：切换打开灯泡。用go语言，给定一个整数数组 bulbs，数组中每个元素都在 1 到 100 之间。共有 100 个电灯泡，编号从 1 到 100

福大大架构师每日一题

发布于 2026-06-24 15:23:56

1020

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-06-14：切换打开灯泡。用go语言，给定一个整数数组 bulbs，数组中每个元素都在 1 到 100 之间。共有 100 个电灯泡，编号从 1 到 100，初始时全部处于关闭状态。

依次遍历数组 bulbs 的每个值 bulbs[i]，对编号为 bulbs[i] 的灯泡执行切换操作：

• 若该灯泡原本关闭，则将其打开；
• 若该灯泡原本打开，则将其关闭。

遍历完成后，收集所有最终处于打开状态的灯泡编号，并按升序排列输出；如果最终没有任何灯泡打开，则返回空列表。

1 <= bulbs.length <= 100。

1 <= bulbs[i] <= 100。

输入： bulbs = [10,30,20,10]。

输出： [20,30]。

解释：

第 bulbs[0] = 10 个灯泡当前是关闭状态，将其打开。

第 bulbs[1] = 30 个灯泡当前是关闭状态，将其打开。

第 bulbs[2] = 20 个灯泡当前是关闭状态，将其打开。

第 bulbs[3] = 10 个灯泡当前是打开状态，将其关闭。

最终，第 20 个和第 30 个灯泡处于打开状态。

题目来自力扣3842。

一、整体执行分步详细过程

阶段1：遍历灯泡操作数组，用哈希map记录每个灯泡切换次数的奇偶性

核心逻辑：灯泡初始全关，切换偶数次=最终关闭，切换奇数次=最终打开；使用异或 ^=1 快速标记奇偶，1代表切换奇数次（亮），0代表偶数次（灭）。

1. 初始化空字典 cnt，用于存储灯泡编号与切换奇偶标记；
2. 读取数组第一个元素 10：
- • 字典中无键10，cnt[10] = 0 ^ 1 = 1；
- • 含义：10号灯泡切换1次，奇数，暂时亮起。当前字典：{10:1}
3. 读取数组第二个元素 30：
- • 字典中无键30，cnt[30] = 0 ^ 1 = 1；
- • 含义：30号灯泡切换1次，奇数，暂时亮起。当前字典：{10:1, 30:1}
4. 读取数组第三个元素 20：
- • 字典中无键20，cnt[20] = 0 ^ 1 = 1；
- • 含义：20号灯泡切换1次，奇数，暂时亮起。当前字典：{10:1, 30:1, 20:1}
5. 读取数组第四个元素 10：
- • 字典已有键10，对应值为1，cnt[10] = 1 ^ 1 = 0；
- • 含义：10号灯泡累计切换2次，偶数，最终熄灭。遍历全部数组后最终字典：{10:0, 30:1, 20:1}

阶段2：筛选所有最终亮起的灯泡

遍历哈希字典里每一组（灯泡编号，标记值）：

1. 键10，值0：标记不大于0，代表切换偶数次，灯泡关闭，舍弃；
2. 键30，值1：标记大于0，切换奇数次，灯泡打开，将30存入结果切片ans；
3. 键20，值1：标记大于0，切换奇数次，灯泡打开，将20存入结果切片ans；筛选完成后，未排序的ans切片内容：[30,20]

阶段3：对结果升序排序

调用排序函数对ans切片从小到大重排：原切片[30,20]排序后变为[20,30]

阶段4：返回并打印结果

函数将排序完成的切片返回，主函数输出最终结果 [20,30]

二、时间复杂度分析

设输入数组长度为 n（题目约束 1 ≤ n ≤ 100），去重后不同灯泡数量最多为 100（灯泡编号1~100）。

1. 第一次遍历输入数组：遍历n个元素，单次map读写O(1)，总耗时 O(n)；
2. 遍历哈希字典筛选亮灯：最多遍历100个键，固定常数 O(1)；
3. 排序结果切片：最多100个元素，常数规模排序 O(1)； 整体时间复杂度：O(n) 常数操作不影响量级，核心耗时仅为遍历输入数组。

三、额外空间复杂度分析

额外开辟的存储空间：

1. map字典cnt：最多存储100组键值对（灯泡编号上限100），固定常量空间；
2. 结果切片ans：最多存放100个亮灯编号，固定常量空间；所有额外空间不受输入数组长度n线性增长，存在固定上限。 整体额外空间复杂度：O(1)

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func toggleLightBulbs(bulbs []int) (ans []int) {
    cnt := map[int]int{}
    for _, i := range bulbs {
        cnt[i] ^= 1
    }
    for i, c := range cnt {
        if c > 0 {
            ans = append(ans, i)
        }
    }
    slices.Sort(ans)
    return
}

func main() {
    bulbs := []int{10, 30, 20, 10}
    result := toggleLightBulbs(bulbs)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from collections import defaultdict

def toggle_light_bulbs(bulbs):
    cnt = defaultdict(int)
    for i in bulbs:
        cnt[i] ^= 1  # 使用异或运算切换0/1状态
    ans = [i for i, c in cnt.items() if c > 0]
    ans.sort()
    return ans

def main():
    bulbs = [10, 30, 20, 10]
    result = toggle_light_bulbs(bulbs)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

std::vector<int> toggleLightBulbs(const std::vector<int>& bulbs) {
    std::map<int, int> cnt;
    for (int i : bulbs) {
        cnt[i] ^= 1;  // 使用异或运算切换0/1状态
    }

    std::vector<int> ans;
    for (const auto& pair : cnt) {
        if (pair.second > 0) {
            ans.push_back(pair.first);
        }
    }
    // map已经按键排序，但为了与Go代码行为一致（Go中map无序需要排序），这里再次排序确保
    // 实际上从map遍历已经是有序的，这行可以省略，但保留以明确意图
    std::sort(ans.begin(), ans.end());
    return ans;
}

int main() {
    std::vector<int> bulbs = {10, 30, 20, 10};
    std::vector<int> result = toggleLightBulbs(bulbs);

    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << result[i];
        if (i < result.size() - 1) {
            std::cout << " ";
        }
    }
    std::cout << std::endl;

    return0;
}