时间戳

首页 > 解决方案 > 有效地将未使用的颜色分配给元素

algorithm - 有效地将未使用的颜色分配给元素

问题描述

我想实现一个功能，可以有效地找到尚未使用的颜色。

假设我有 3 种颜色（例如“红色”、“绿色”、“蓝色”）可用。该功能的作用是当用户点击一个按钮时，系统会添加一个图标并为其分配一个没有使用过的颜色。用户可以在任何给定时间更改图标的颜色或删除任何图标。如果所有颜色都已使用，那么它只会分配“红色”颜色。

我知道如果颜色只能分配一次，则可以使用 Stack 结构有效地完成该功能，但是由于用户可以更改图标的颜色，因此我想不出一种利用 Stack 结构的方法。可能发生的一种情况是，用户添加了第一个图标并将图标分配为红色，然后用户添加了第二个图标，但手动将图标颜色更改为红色。那么当用户尝试添加第三个图标时，如何找到可用的颜色呢？

目前，我拥有的是一个对象/字典，键是颜色，值是一个数组，其中包含颜色已分配给的图标。例如{'red': [icon1, icon2], 'blue': [], 'green: []}。然后，当用户添加图标时，我将遍历 Object 的键并检查值数组是否为空。但是，我觉得这在计算上很昂贵，因为对于每种颜色，我都需要遍历对象并检查其值。

我正在用 JavaScript 实现这个功能，但是，我正在寻找一种通用算法来解决这个问题。

标签： algorithmsorting

解决方案

如果只有几个颜色或按钮（比如少于 1000 个，以较少者为准），那么您的算法的效率可能并不重要，只需将值或按钮收集到一个列表中并依次检查每个列表以查看它是否每当您需要另一种颜色时，其中都有任何值是实用的

这将是O(n)迭代整个集合的最坏情况

如果您已经将按钮收集到一个集合中（这可能与您显示它们的方式有关），则迭代此集合以检查某些颜色成员并在您拥有颜色集合的每个成员时停止可能比单独保留一个更有效使用的颜色列表，但这将取决于语言和实现

在这种情况下，一个有效的解决方案可能是使用一个集合并检查它的长度

colors_total = set(colors)
colors_used  = set()

color = null

for button in buttons:
    colors_used.add(button.color)
    if len(colors_used) >= len(colors_total):
        color = red
        break

if not color:
    color = colors_total.set_subtract(colors_used)[index0]

推荐阅读