6

在我的一次采访中，面试官问我 - 一些大小的数组包含随机混合的红色、蓝色和绿色球。像 RGBBBRRGGG，其中 RGB 代表红色、绿色和蓝色。

以RRRRGGGGBBBB 之类的数组结束的最佳方式是什么，即所有R、所有G 和所有B 一起。

我建议将所有红色、蓝色、绿色转换为它们的 ASCII 值，然后在其上运行最有效的排序算法。但他不为所动。这个问题还有其他更有效的解决方案吗？具有最低的空间和时间复杂度 ?

4

7 回答 7

15

只需遍历数组并分别计算 和 的出现R次数。然后，输出字符串。线性时间。GB

于 2012-08-11T06:31:30.240 回答
9

面试官可能想知道你是否熟悉荷兰国旗问题。它有一个简单的线性解决方案。C++维基百科页面上有Java示例。

于 2012-08-11T08:05:25.160 回答
0

编辑我可能误解了你的问题

您希望将 RGB 值转换为 HSL 值。然后，您将知道色调会告诉您它最接近的颜色，从而确定它属于哪个 R/G/B 部分。然后您可以更进一步，考虑色调、饱和度和照明来确定它们的确切顺序彼此之间，相对于整个阵列。

于 2012-08-11T06:33:22.213 回答
0

此外，如果您可以像“4R4G4B”那样保存，则可以有效地保存它

于 2012-08-11T06:33:53.127 回答
0

这个问题很容易在线性时间内完成。为了进一步改进算法，您可以创建一个计数器数组 int[3]，并让 counter[0]、counter[1] 和 counter[2] 分别计算红色、绿色和蓝色。因此，您只需遍历数组一次。

另一个最小化空间复杂度的解决方案是使用 3 个指针：current、rg 和 gb。指针 current 表示您当前正在查看的数组位置， rg 和 gb 分别是 red / green 和 green / blue 之间的边界。初始化 current = 0，rg = -1，gb = n，其中 n = A 的大小。

而 gb>current - 如果 A[i] == R，将 rg 向右移动 1，并将 current 替换为 rg - 否则，如果 A[i] == blue，将 fb 向左移动 1，将 current 替换为 gb - 否则，什么都不做

空间复杂度 = O(n)，因为您没有使用任何额外的数组时间复杂度 = O(n)，每个元素最多交换一次

于 2015-03-11T19:14:33.557 回答
0

Python 解决方案

input = [1, 0, 2, 2, 1, 0, 1, 2, 0, 0, 2, 1, 2, 0, 0]

output = []
for i in input:
    if i == 0:
        output.insert(0, i)
    elif i == 2:
        output.append(i)
    else:
        if output.count(2) > 0:
            index = output.insert(output.index(2), i)
        else:
            output.append(i)

print(output)
于 2019-08-11T12:49:06.397 回答
0

此解决方案需要 O(n)：

def sort_Colors(arr):
    first = 0
    mid = 0
    last = len(arr)-1
    while mid <= last:
        if arr[mid] == 0:
            arr[first] , arr[mid] = arr[mid], arr[first]
            first += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[last] = arr[last], arr[mid]
            last -= 1
    return arr

输入 = [1, 2, 0, 1, 0, 1, 2, 0, 0, 0, 0]

输出 = [0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2]

于 2020-04-03T16:07:58.590 回答