2021-10-06|閱讀時間 ‧ 約 2 分鐘

【LeetCode】977. Squares of a Sorted Array

今天的題目示例如下:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100]
簡單來說,要的輸出結果是把陣列內每個數字取平方後,對陣列做排序。
使用內建的排序方法
使用內建的排序方法
如此一來是完成了沒錯,但...好像什麼都沒練到。於是用了時間複雜度O(nlogn)的合併排序法練習,替代了排序的部分。
採用mergeSort
合併排序法採遞迴的方式,將原本的陣列從中間分成左右兩半,比較取值後覆寫回原本的陣列。
建立兩個新的陣列(左子陣列、右子陣列)
比較左右子陣列,依序放入原陣列覆寫
提交出的結果效能時間跟空間使用都很穩定,穩定的輸給內建的排序。
另外,取平方的作法原則上可以使用Math.pow() 得到次方結果,型態是double。印象中以前課堂上特別被點出,如果只是取平方的需求,讓數字跟自己相乘就好,次方函數的運作採用類似泰勒展開的近似法趨近,效能上還是有差別。
分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.