Day19 Leetcode Array系列---- Squares of a Sorted Array

本次題目 Squares of a Sorted by JS

題目給予一串數字陣列，將其元素平方並且排序成新的陣列

input1= [-4,-1,0,3,10]
output1= [0,1,9,16,100]

input2= [-7,-3,2,3,11]
output2= [4,9,9,49,121]

思考路線 1

1. 先用 map 把每個元素平方
2. 用 sort 把元素排大小

Coding Time

第一個寫法很直覺，但是時間複雜度高，因為使用 map 已經跑過一輪迴圈，之後的 sort 又跑了很多次迴圈去排列大小

input1= [-4,-1,0,3,10]
output1= [0,1,9,16,100]

input2= [-7,-3,2,3,11]
output2= [4,9,9,49,121]

const squaresAndSort = ary => ary.map( x => x**2)
                                 .sort( (x,y)=>{return x-y})

const expect = (a,b) =>{ console.log(JSON.stringify(a)==JSON.stringify(b))}

expect(squaresAndSort(input1),output1)
expect(squaresAndSort(input2),output2)

思考路線 2

1. 用兩根指針前後逼近至中間
2. 將這兩根指針取到值，取絕對值比大小，將大的值平方夾到 result 的前端
3. 取到大的值的指針會往中間移動

Coding Time 2

設定前後兩根指針 (start,end)

取到的值取絕對值比大小，使用 unshift 把平方後的元素放進 result並移動指針

function squaresAndSort2(ary){
    let start = 0
    let end = ary.length-1
    result = []
    while(start<=end){
        if( Math.abs(ary[start]) > Math.abs(ary[end]) ){
            result.unshift(ary[start]**2)
            start +=1
        }else{
            result.unshift(ary[end]**2)
            end -= 1
        }
    }
    return result
}

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty