LeetCode.977-排序數組的平方(Squares of a Sorted Array)

這是悅樂書的第369次更新，第397篇原創

01看題和準備

今天介紹的是LeetCode算法題中Easy級别的第231題（順位題号是977）。給定一個整數數組A按有序遞增順序排序，傳回每個數字的平方，也按有序遞增順序傳回。例如：

輸入：[ - 4，-1,0,3,10]

輸出：[0,1,9,16,100]

輸入：[ - 7，-3,2,3,11]

輸出：[4,9,9,49,121]

注意：

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• A按有序遞增順序排序。

02 第一種解法

直接翻譯題目即可，借助

Arrays

的

sort

方法來對結果數組排序。

此解法的時間複雜度是

O(N log(N))

，空間複雜度是

O(N)

。

public int[] sortedSquares(int[] A) {
    int n = A.length, i = 0;
    int[] result = new int[n];
    for (int num : A) {
        result[i++] = num*num;
    }
    Arrays.sort(result);
    return result;
}
           

03 第二種解法

不使用新數組來作為結果數組傳回，将

A

中的負數變正數，再排序，再取平方。

O(N log(N))

O(1)

public int[] sortedSquares2(int[] A) {
    int n = A.length;
    for (int i=0; i<n; i++) {
        A[i] = A[i]<0 ? -A[i] : A[i];
    }
    Arrays.sort(A);
    for (int j=0; j<n; j++) {
        A[j] = A[j]*A[j];
    }
    return A; 
}
           

04 第三種解法

使用計數排序，對

A

中的數進行處理，然後計算平方。

O(N)

O(N)

public int[] sortedSquares3(int[] A) {
    int n = A.length, index = 0;
    int[] sort = new int[10001];
    int len = sort.length;
    for (int i=0; i<len; i++) {
        sort[i] = 1;
    }
    for (int num : A) {
        sort[num<0 ? -num : num]++;
    }
    int[] result = new int[n];
    for (int j=0; j<sort.length; j++) {
        if (sort[j] > 1) {
            while (sort[j]-1 > 1) {
                result[index++] = j*j;
                sort[j]--;
            }
            result[index++] = j*j;
        }
    }
    return result;
}
           

05 第四種解法

雙指針，前後比較兩個數，如果前面的數的絕對值大于後面的數，那麼結果數組中目前位元素為前面的元素平方，反之就是後面的元素平方為結果數組目前位元素。

O(N)

O(N)

public int[] sortedSquares4(int[] A) {
    int n = A.length;
    int start = 0, end = n-1;
    int[] result = new int[n];
    for (int i=n-1; i>=0; i--) {
        if (Math.abs(A[start]) > Math.abs(A[end])) {
            result[i] = A[start]*A[start];
            start++;
        } else {
            result[i] = A[end]*A[end];
            end--;
        }
    }
    return result;
}
           

06 小結

算法專題目前已連續日更超過七個月，算法題文章

237

+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！