前言說明

算法學習，日常刷題記錄。

題目連接

有序數(shù)組的平方

題目內容

給你一個按非遞減順序排序的整數(shù)數(shù)組nums，返回每個數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序。

示例1:

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

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

解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]

排序后，數(shù)組變?yōu)?[0,1,9,16,100]

示例2:

輸入：nums = [-7,-3,2,3,11]

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

提示:

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

nums 已按非遞減順序排序

進階：

請你設計時間復雜度為O(n)的算法解決本問題

分析過程

利用雙指針解決。

左指針從數(shù)組左側開始，右指針從數(shù)組右側開始，兩個指針從數(shù)組兩端往中間移動，直到兩個指針相等，結束循環(huán)。

每次循環(huán)時，結果數(shù)組results只取較大的數(shù)，被取了數(shù)的一側指針向中間移動一位，接著數(shù)組results再取較小的數(shù)，這側的指針再向中間移動一位。

雖然是左右指針同時向中間移動，但是每次都會取兩次的數(shù)，pos游標已經(jīng)移動了兩次，所以最后剛好構造出和數(shù)組nums的長度一致的結果數(shù)組results。

因為數(shù)組nums的絕對值兩側最大，往里越來越小，所以構造結果數(shù)組results時，從后往前構造，剛好就是非遞減數(shù)組。

解答代碼

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 獲取數(shù)組nums長度
        int n = nums.length;

        // 定義結果數(shù)組results
        int[] results = new int[n];

        // 用雙指針遍歷數(shù)組nums，從數(shù)組nums兩邊往里遍歷，每次結果數(shù)組results只取大的數(shù)，結果數(shù)組results從后往前填滿，直到兩個指針游標相等
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                // 若前指針i的位置的元素的平方大于后指針j的位置的元素的平方，那么前指針i移動
                results[pos] = nums[i] * nums[i];
                ++i;
            } else {
                // 若前指針i的位置的元素的平方小于等于后指針j的位置的元素的平方，那么后指針j移動
                results[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }

        return results;
    }
}

提交結果

執(zhí)行用時1ms，時間擊敗100.00%的用戶，內存消耗40.2MB，空間擊敗57.04%的用戶。

運行結果

原文鏈接

原文鏈接：有序數(shù)組的平方