這是悅樂(lè)書(shū)的第369次更新，第397篇原創(chuàng)

01看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第231題（順位題號(hào)是977）。給定一個(gè)整數(shù)數(shù)組A按有序遞增順序排序，返回每個(gè)數(shù)字的平方，也按有序遞增順序返回。例如：

輸入：[ - 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方法來(lái)對(duì)結(jié)果數(shù)組排序。

此解法的時(shí)間復(fù)雜度是O(N log(N))，空間復(fù)雜度是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 第二種解法

不使用新數(shù)組來(lái)作為結(jié)果數(shù)組返回，將A中的負(fù)數(shù)變正數(shù)，再排序，再取平方。

此解法的時(shí)間復(fù)雜度是O(N log(N))，空間復(fù)雜度是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 第三種解法

使用計(jì)數(shù)排序，對(duì)A中的數(shù)進(jìn)行處理，然后計(jì)算平方。

此解法的時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是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 第四種解法

雙指針，前后比較兩個(gè)數(shù)，如果前面的數(shù)的絕對(duì)值大于后面的數(shù)，那么結(jié)果數(shù)組中當(dāng)前位元素為前面的元素平方，反之就是后面的元素平方為結(jié)果數(shù)組當(dāng)前位元素。

此解法的時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是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 小結(jié)

算法專(zhuān)題目前已連續(xù)日更超過(guò)七個(gè)月，算法題文章237+篇，公眾號(hào)對(duì)話(huà)框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！