javascript - 在 O(n) 时间内对 (1,2,3) 个数字的数组进行排序

Question

给定一个只有 3 个唯一数字(1、2、3)的数字列表，在 O(n) 时间内对列表进行排序。加上使用常量空间 O(1) 对数组进行排序。

示例:

输入:[3, 3, 2, 1, 3, 2, 1]

输出:[1, 1, 2, 2, 3, 3, 3]

这里是我做的解决方案(没有 O(1) 空间并且在数组中有空格空间..): 这个函数的作用很简单..在所有元素都是2的情况下，将排列的大小增加一倍；然后它转到其先前的长度(当前/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

您可以使用 Dutch national flag problem 的算法:

The Dutch national flag problem ¹ is a computer science programming problem proposed by Edsger Dijkstra (In a chapter of his book A Discipline of Programming Prentice-Hall, 1976). The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

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);