Leetcode 977 - Squares of a Sorted Array

題目

Problem#

題目給你一個遞增排序的

follow-up: 用 $\mathcal{O}(N)$ 實作

想法#

$\mathcal{O}(N\log{N})$ 實作就把東西都平方然後 sort 就好。
$\mathcal{O}(N)$ 作法可以觀察平方後的排序，負的數字平方會是遞減，反之正的是遞增，就用雙指標把兩個合併即可

• 時間複雜度: $\mathcal{O}(N)$
• 空間複雜度: $\mathcal{O}(N)$

AC Code#

賞析#

• 邊比較邊平方
  • https://leetcode.com/problems/squares-of-a-sorted-array/discuss/973576/A-good-interview-problem-interview-explanation-C%2B%2B

心得#

None