颜色排序问题

在排序颜色问题中，我们给出一个包含三种数字的数组。假设这些数字是 0、1 和 2。我们的任务是编写一个程序来对这些数字进行排序。排序后，数组将首先包含所有 0，然后是 1，最后是 2。让我们通过一些示例来理解这个问题。

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

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

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

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

暴力破解法

最直接的方法是使用任何排序算法来排序数组。一个好的排序算法的平均时间复杂度为 log n，其中 n 是给定数组的大小。然而，我们可以将时间复杂度优化到线性时间复杂度。

方法 - 1

我们将使用两个指针来解决这个问题。

数组可以分为四个区域，用于存储三种颜色 0、1 和 2。我们将初始化三个指针 l = 0，m = 0，h = 数组的最后一个索引。

• array[0] 到 array[l - 1]
• array[l] 到 array[m - 1]
• array[m] 到 array[h - 1]
• array[h] 到 array[n]

我们将根据 i 元素执行三个操作。

1. 如果当前元素是 0，则将其与较低索引处的元素交换。
2. 如果当前元素是 1，则不做任何更改，并移至下一个元素。
3. 如果当前元素是 2，则将其与较高索引处的元素交换。

让我们看一个例子来理解这个程序将如何工作。

array = [1, 0, 1, 2, 0, 1, 1]

l = 0, m = 0, h = 6

步骤 - 1

array[m] == 1

m = m + 1 = 1

array = [1, 0, 1, 2, 0, 1, 1]

步骤 - 2

array[m] = 0

swap(array[l], array[m])

m = m + 1 = 2

l = l + 1 = 1

array = [0, 1, 1, 2, 0, 1, 1]

步骤 - 3

array[m] == 1

m = m + 1 = 3

array = [0, 1, 1, 2, 0, 1, 1]

步骤 - 4

array[m] == 2

swap(array[m], array[h])

h = h - 1 = 5

array = [0, 1, 1, 0, 1, 1, 2]

步骤 - 5

array[m] == 0

swap(array[l], array[m])

m = m + 1 = 4

l = l + 1 = 2

array = [0, 0, 1, 1, 2, 2]

步骤 - 6

array[m] == 2

swap(array[m], array[h])

h = h - 1 = 4

array = [0, 0, 1, 1, 2, 2]

步骤 - 7

array[m] == 2

swap(array[m], array[h])

h = h - 1 = 3

array = [0, 0, 1, 1, 2, 2]

因此，排序后的数组为 array = [0, 0, 1, 1, 2, 2]。

以下是解决此问题需要遵循的步骤。

• 我们将初始化三个变量作为三个指针。它们是 l = 0，m = 0，h = N。
  • 整个数组将分为四个部分，从第 0 个索引到 l，这一部分将包含 0。
  • 下一部分是 l - m，这个范围将包含 1。
  • 下一部分 m - h 将包含未知数字，最后一部分 h - N 将包含 2。
• 我们将遍历给定数组，从第 0 个索引开始。循环将持续到中间索引 m 小于高索引 h 为止。
• 如果当前元素是 0，则将其与指针 l 处的元素交换。然后我们将 m 和 l 分别加 1。
• 如果当前元素是 1，则保持数组不变，并将中间指针加 1。
• 最后，如果当前元素是 2，我们将再次交换元素。这次我们将 2 与高索引或 h 指针处的元素交换。
  • 现在我们不会更新 m 指针，因为当前元素可能是 0，我们需要将其与较低索引处的元素交换。因此，我们只通过将 h 指针减 1 来更新它。
• 在这些操作的最后，数组将被排序，然后我们将打印数组。

代码

输出

The sorted array is:
0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2  

时间复杂度： 由于我们使用了线性循环，因此该方法的时间复杂度为 O(n)。

空间复杂度： 由于我们修改了原始数组，因此该方法空间复杂度为常数，即 O(1)。

方法 - 2

在此方法中，我们将使用计数方法对数组进行排序。

• 我们将初始化三个变量 count0、count1 和 count2。
• 现在，我们将遍历给定数组，并计算每个数字或颜色的出现次数。
• 最后，我们将根据数字的计数来存储颜色或数字。

让我们看一个例子来理解解决方案。

array = [0, 1, 0, 1, 2, 0, 1, 1, 2]

count0 = 0, count1 = 0, count2 = 0

在 n = 0 时：array[0] == 0

count0 += 1

# count0 = 1

在 n = 1 时：array[1] == 1

count1 += 1

# count1 = 1

在 n = 2 时：array[2] == 0

count0 += 1

# count0 = 2

在 n = 3 时：array[3] == 1

count1 += 1

# count1 = 2

在 n = 4 时：array[4] == 2

count2 += 1

# count2 = 1

在 n = 5 时：array[5] == 0

count0 += 1

# count0 = 3

在 n = 6 时：array[6] == 1

count1 += 1

# count1 = 3

在 n = 7 时：array[7] == 1

count1 += 1

# count1 = 4

在 n = 8 时：array[8] == 2

count2 += 1

# count2 = 2

# 创建一个包含 count0 个 0，count1 个 1 和 count2 个 2 的数组。

因此，排序后的数组为 [0, 0, 0, 1, 1, 1, 1, 2, 2]。

我们将遵循以下步骤来解决上述方法的问题。

• 初始化三个计数器，count0 计算 0 的数量，count1 计算 1 的数量，count2 计算数组中 2 的数量。
• 下一步是找出 count0、count1 和 count2 的值。为了找到计数，我们将遍历数组，并使用 if-else 条件来计算数组中 0、1 和 2 出现的次数。
• 最后一步是创建一个包含适当数量的 0、1 和 2 的数组。

以下是上述方法的 Python 程序。

代码

输出

The sorted array is:
0 0 0 0 0 0 1 1 1 1 1 1 2 2 2

时间复杂度： 此程序中没有使用嵌套循环。仅使用了线性循环。因此，时间复杂度也是线性的，即 O(N)。

空间复杂度： 我们创建了一个数组来存储排序后的数组。因此，空间复杂度是线性的，即 O(N)。

方法 - 3

我们可以修改上述方法，并将空间复杂度降低到常数。

在找到 0、1 和 2 的计数后，我们将执行以下步骤，而不是创建一个新数组。

• 将数组的前 m 个元素替换为 0，其中 m = count0 = 3。

array = [0, 0, 0, 1, 2, 0, 1, 1, 2]

• 将数组接下来的 m 个元素替换为 1，其中 m = count1 = 4。

array = [0, 0, 0, 1, 1, 1, 1, 1, 2]

• 将数组接下来的 m 个元素替换为 2，其中 m = count2 = 2。

array = [0, 0, 0, 1, 1, 1, 1, 2, 2]

因此，排序后的数组为 [0, 0, 0, 1, 1, 1, 1, 2, 2]。

因此，算法的最后一步将是运行三个 while 循环，其中迭代次数等于相应计数值，并将 0、1 和 2 存储在原始数组中。

以下是上述算法的 Python 程序。

代码

输出

The sorted array is:
0 0 0 0 0 0 1 1 1 1 1 1 2 2 2  

时间复杂度 - 与之前相同，O(N)。

空间复杂度： 我们更新了给定的数组；因此，我们没有使用任何额外的空间来存储排序后的数组。因此，空间复杂度为常数，即 O(1)。