algorithm - 惯用 Go 中 set 的最小值

Question

如何在 go 中编写返回集合最小值的函数？我不只是在寻找解决方案(我知道我可以在遍历第一个元素时只初始化最小值，然后设置一个我初始化最小值的 bool 变量)，而是一个惯用的解决方案。由于 go 没有原生集，假设我们有一个 map[Cell]bool。

Answer 1

Map 是 Go 中实现集合的惯用方式。惯用代码使用 bool 或 struct{} 作为映射的值类型。后者使用的存储空间较少，但需要在键盘上输入更多内容才能使用。

假设单元格的最大值为 maxCell，则此函数将计算最小值:

func min(m map[Cell]bool) Cell {
    min := maxCell
    for k := range m {
        if k < min {
            min = k
        }
    }
    return min
}

如果 Cell 是数字类型，那么 maxCell 可以设置为 math constants 之一.

任何使用 map 的解决方案都需要对键进行循环。

你可以保留一个heap除了 map 找到一个最小值。这将需要更多的存储空间和代码，但效率会更高，具体取决于集合的大小和调用最小函数的频率。