O（n）时间中的（1,2,3）个数字的排序数组

Question

给定一个只有3个唯一数字（1、2、3）的数字列表，请以O（n）时间对列表进行排序。另外，使用常量空间O（1）对数组进行排序。

例：

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

在这里，我提出的解决方案（没有O（1）空间，并且在数组中没有空的空间..）：此函数的作用很简单..在所有元素均为2的情况下，将排列的大小增加了一倍; 然后它返回其先前的长度（current / 2）对其元素进行排序..如果为1，则不执行任何操作，如果找到2，则将其放入先前的最大长度+ 1，它增加变量len并消除元素，如果它是3，则推并删除该元素..则您在数组中有空位，并且不满足问题的要求，但它是O（n）。

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))

Answer 1

您可以使用荷兰国旗问题的算法：

荷兰国旗问题 ¹是由Edsger Dijkstra提出的计算机科学编程问题（在他的《编程学徒的纪律》一书的一章中，1976年）。荷兰的国旗由三种颜色组成：红色，白色和蓝色。给定这三种颜色的球随机排列在一条直线上（球的实际数量无关紧要），任务是将它们排列成所有相同颜色的球都在一起并且它们的集体颜色组以正确的顺序排列。

var array = [3, 3, 2, 1, 3, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (array[j] < MID) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (array[j] > MID) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);