LeetCode #977 Squares of a Sorted Array 已排序陣列的平方

英文原文如下

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

中文翻譯

給予一個正冪排列的整數陣列 nums，回傳一個將所有數字平方後，以正冪排列的陣列。

範例及題目限制

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

進一步: 將每個元素平方後再排列新的陣列是非常容易解決的，你可以找到一個別的方法使用  O(n) 的時間複雜度嗎?

解題思路

最開始，肯定是先求有再求好

先來試著平方後再排序吧~

常見的有兩種作法，分別是 for 迴圈以及 LINQ

C# 解決方案

⚠️方案1

public class Solution {
    public int[] SortedSquares(int[] nums) {
        for(int i=0; i<nums.Length; i++){
            nums[i]*=nums[i];
        }

        Array.Sort(nums);

        return nums;
    }
}

時間複雜度: O(n log n) >> Array.Sort快速排序法的時間複雜度

⚠️方案1.1 – LINQ

public class Solution {
    public int[] SortedSquares(int[] nums) {
        var newNums = nums.Select(x => x * x).ToArray();

        Array.Sort(newNums);

        return newNums;
    }
}

時間複雜度: O(n log n)

這時候，讓我們來探索一下該怎麼用一個迴圈來解決

首先，已知本來的陣列已經排序過了

要是全部都是正整數，那就簡單了，可以直接平方不用管

這一題因為涵蓋了 <0 的負數

轉念一想，負的也可以比較啊!! 直接比較絕對值就可以知道誰應該放在比較後面了~

我們可以使用兩個指標(two pointers)分別指向第一個元素以及最後一個元素，以及一個 nowIdx 對應著新陣列目前填充的索引 ➡ 新的陣列由最後開始往前填充，因為負數的最左邊以及正數的最右邊平方都是最大的，往中間是比較小的

兩個指標對應的元素誰的絕對值較大，誰的平方就會被放在對應的新陣列中

⭐方案2

public class Solution {
    public int[] SortedSquares(int[] nums) {
        
        int i = 0;
        int j = nums.Length-1;
        int nowIdx = nums.Length-1;
        int[] newNums = new int[nums.Length];

        while(i<=j){
            var iNum = nums[i];
            var jNum = nums[j];

            if(Math.Abs(iNum)>Math.Abs(jNum)){
                newNums[nowIdx] = iNum*iNum;
                i+=1;
            }
            else {
                newNums[nowIdx] = jNum*jNum;
                j-=1;
            }
            nowIdx-=1;
        }

        return newNums;
    }
}

時間複雜度: O(n)

整體架構上用了while迴圈，並設下的條件是 while(i<=j)

也就是當右邊的指標大於左邊的，就會持續進行，故剛好會跑 nums 的長度次

結論

兩個指標的作法其實通常會出現在中階的題目上，這次難得在簡單的題型的進一步中看到

是個磨練想法的好機會呢~

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Squares of a Sorted Array – LeetCode

一些隨機的LeetCode文章