LeetCode 每日一題(day 1)
題目描述:
給定一個按非遞減順序排序的整數陣列 A,返回每個數字的平方組成的新陣列,要求也按非遞減順序排序。
示例 1:
輸入:[-4,-1,0,3,10] 輸出:[0,1,9,16,100]
示例 2:
輸入:[-7,-3,2,3,11] 輸出:[4,9,9,49,121]
提示:
- 1<= A.length <= 10000
- -10000 <= A[i] <= 10000
- A 已按非遞減順序排序。
解決方案
方法一:排序
思路與演算法
建立一個新的陣列,它每個元素是給定陣列對應位置元素的平方,然後排序這個陣列。
public int[] sortedSquares(int[] A) { int[] B = new int[A.length]; for (int i=0; i < A.length; i++) { B[i] = (A[i]) * (A[i]); } Arrays.sort(B); return B; }
複雜度分析
-
時間複雜度:O(N \log N)O(NlogN),其中 NN 是陣列 A 的長度。
-
空間複雜度:O(N)O(N)。
方法二:雙指標
思路
因為陣列 A 已經排好序了, 所以可以說陣列中的負數已經按照平方值降序排好了,陣列中的非負數已經按照平方值升序排好了。
舉一個例子,若給定陣列為 [-3, -2, -1, 4, 5, 6],陣列中負數部分 [-3, -2, -1] 的平方為 [9, 4, 1],陣列中非負部分 [4, 5, 6] 的平方為 [16, 25, 36]。我們的策略就是從前向後遍歷陣列中的非負數部分,並且反向遍歷陣列中的負數部分。
演算法
我們可以使用兩個指標分別讀取陣列的非負部分與負數部分 —— 指標 i 反向讀取負數部分,指標 j 正向讀取非負數部分。
那麼,現在我們就在使用兩個指標分別讀取兩個遞增的陣列了(按元素的平方排序)。接下來,我們可以使用雙指標的技巧合並這兩個陣列。
public int[] sortedSquares(int[] A) { int N = A.length; int j = 0; while (j < N && A[j] < 0) j++; int i = j-1; int[] ans = new int[N]; int t = 0; while (i >= 0 && j < N) { if (A[i] * A[i] < A[j] * A[j]) { ans[t++] = A[i] * A[i]; i--; } else { ans[t++] = A[j] * A[j]; j++; } } while (i >= 0) { ans[t++] = A[i] * A[i]; i--; } while (j < N) { ans[t++] = A[j] * A[j]; j++; } return ans; }