排颜色 (经典算法题500道),程序员经典面试笔试题目, 码小课

当前位置：面试刷题>> 排颜色 (经典算法题500道)

题目描述补充

题目：排颜色

给定一个整数数组 colors，其中每个元素代表一个颜色的编号，要求对这些颜色进行重新排序，使得相同颜色的编号在数组中相邻，并且颜色的相对顺序与原始数组中的相对顺序保持一致（即稳定排序）。

例如，输入数组 colors = [2, 1, 2, 3, 3, 2]，则一种可能的输出是 [1, 2, 2, 2, 3, 3]，这里 1、2 和 3 都各自聚集在一起，并且保持了它们在原数组中的相对顺序。

解题思路

这个问题可以通过使用计数排序（Counting Sort）的思想来解决，但由于计数排序本身不保持稳定性，我们需要稍微修改它以保持稳定性。由于颜色编号的范围可能不是连续的，我们可以使用哈希表（或数组，如果颜色编号范围较小且连续）来记录每个颜色编号的出现次数，并使用一个额外的数组来保存排序后的结果。

示例代码

PHP 示例

function sortColors($colors) {
    $count = array_fill(0, max($colors) + 1, 0); // 初始化计数数组
    $index = 0;

    // 计数
    foreach ($colors as $color) {
        $count[$color]++;
    }

    // 根据计数结果和原始顺序填充结果数组
    foreach ($count as $color => $freq) {
        while ($freq-- > 0) {
            $colors[$index++] = $color;
        }
    }

    return $colors;
}

// 示例
$colors = [2, 1, 2, 3, 3, 2];
$sortedColors = sortColors($colors);
print_r($sortedColors);

Python 示例

def sortColors(colors):
    count = [0] * (max(colors) + 1)
    for color in colors:
        count[color] += 1
    
    index = 0
    for color, freq in enumerate(count):
        while freq > 0:
            colors[index] = color
            index += 1
            freq -= 1

# 示例
colors = [2, 1, 2, 3, 3, 2]
sortColors(colors)
print(colors)

JavaScript 示例

function sortColors(colors) {
    const count = new Array(Math.max(...colors) + 1).fill(0);
    let index = 0;

    // 计数
    for (let color of colors) {
        count[color]++;
    }

    // 根据计数结果和原始顺序填充原数组
    for (let color = 0; color < count.length; color++) {
        while (count[color]-- > 0) {
            colors[index++] = color;
        }
    }

    return colors;
}

// 示例
let colors = [2, 1, 2, 3, 3, 2];
sortColors(colors);
console.log(colors);

注意：以上代码直接修改了输入的 colors 数组，如果需要保留原数组，可以先复制一份再操作。