时间戳

首页 > 解决方案 > 生成以下结果的更好算法是什么？

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

问题描述

我们有一个具有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]);

如果您有任何想法像不使用其他变量一样进行优化，请帮助我（它将降低空间复杂度）。谢谢

标签： javascriptalgorithmdata-structureslogic

解决方案

您不需要对数组进行排序。只需对数组进行一次传递，并且在每个步骤中仅修复 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]。

推荐阅读