javascript - 生成以下结果的更好算法是什么？

Question

我们有一个包含 n 个数字(非零)的数组输入，即

input--> [a1, a2, a3, a4, a5, ...., aN] (not in order)

现在我们希望输出为

output--> Ai <= Aj >= Ak <= Al >= Am <= ....An.

我已经为这个问题写了一个代码，它很好但没有优化如果我谈论时间和空间复杂性那么它一定不是好的解决方案。

function test(array){
    if(array && array.length){
        let newArray = [];
        array = array.sort();
        let m;
        if(array.length % 2){
            m = (array.length +1 )/2;
        }else{
            m = (array.length)/2;
        }
        newArray.push(array[m-1]);
        for(let i=1;i<=m;i++){
            if(array[m-1+i])
            newArray.push(array[m-1+i]);
            if(array[m-1-i])
            newArray.push(array[m-1-i]);
        }
        console.log(newArray);
        return newArray;
    }else{
        throw 'invalid argument';
    }
}

test([1,2,3,4]);

如果您有任何关于不使用其他变量的优化想法(它将降低空间复杂度)，请帮助我。谢谢

Answer 1

您不需要对数组进行排序。只需遍历数组，并且在每个步骤中只修复 a[i]、a[i+1]。

假设 a[1] <= a[2] >= a[3]...<= a[i-1] >= a[i]

现在，如果 a[i] <= a[i+1]，继续增加 i。

如果 a[i] > a[i+1]，交换它们。

对称地，当 i 为偶数时，如果 a[i] < a[i+1] 交换 a[i],a[i+1]。