#977. Squares of a Sorted Array

題目描述

給你一個非降序排列的整數陣列nums，回傳陣列中元素的平方並同樣以非降序排列。

限制條件

1. 1 <= nums.length <= 10^4
2. -10^4 <= nums[i] <= 10^4
3. nums以非降序排列。

解題思路

Square Each Element and Sort

最簡單的按照題目要求，先平方每個元素，再來因為小於0的數字平方後會是正的，因此需要整理過陣列才能回傳。

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

複雜度分析：

• 時間複雜度：平方每個元素是O(n)，Sort(n)是O(n log n)，因此時間複雜度為O(n log n)。
• 空間複雜度：空間複雜度為O(1)。

Follow-up

將每個元素平方後再盡情整理非常的容易，你可以設計出複雜度為O(n)的不同的解決辦法嗎？

Two Pointers

要讓複雜度為O(n)的話，用in-place的方式顯然不好處理，所以我們會需要額外的空間來放置答案。

由於正負值的平方都有可能會是較大的那一邊，因此正值與負值要先比較過才能放入答案中。 所以這邊使用雙指標，一邊從左邊開始檢查，另一邊則從右邊開始檢查。 先讓兩邊都取絕對值比大小，把較大的一邊找出來，平方後放入答案中，然後取出值的那一邊的指標往前移動，直到指標相遇為止。

public class Solution { 
	public int[] SortedSquares(int[] nums) {
        int[] ans = new int[nums.Length];
        int left=0;
        int right= nums.Length-1;
        int curr = nums.Length-1;
        while(left<=right){
            if(Math.Abs(nums[left])>Math.Abs(nums[right])){
                ans[curr] = nums[left]*nums[left];
                left++;
            }else{
                ans[curr] = nums[right]*nums[right];
                right--;
            }          
            curr--; 
        }
        return ans;
    }
}

複雜度分析：

• 時間複雜度：雙指標還是要處理所有的元素，因此時間複雜度為O(n)。
• 空間複雜度：增加了一個用來放答案的陣列，因此空間複雜度為O(n)。

學習重點

• Sorting
• Two Pointers