Brooke

一、題目

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

 

Example 1:

Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

 

二、程式作法

/*寫法一*/
public class Solution
{
    public int[] SortedSquares(int[] nums)
    {
        int left = 0;
        int right = nums.Length - 1;
        int[] res = new int[nums.Length];
        int index = nums.Length - 1;

        while (left <= right)
        {
            if (nums[left] * nums[left] <= nums[right] * nums[right])
            {
                res[index] = nums[right] * nums[right];
                right--;
            }
            else
            {
                res[index] = nums[left] * nums[left];
                left++;
            }
            index--;
        }
        return res;
    }
}

/*寫法二*/
/*
public class Solution
{
    public int[] SortedSquares(int[] nums)
    {
        List<int> collection = new List<int>();
        int[] result = new int[nums.Length]; ;

        for (int i = 0; i < nums.Length; i++)
        {
            int temp = nums[i] * nums[i];
            collection.Add(temp);
        }

        collection.Sort();

        for (int i = 0; i < collection.Count; i++)
        {
            result[i] = collection[i];
        }
        return result;
    }
}
*/

 

三、思路筆記

題目要做的是，對陣列裡每一個元素值做平方再排序，但時間複雜度要 O(n)。

一開始的想法為對每一個元素先做平方，然後再做排序，這是個解法。

另一種解法為，由於 nums 陣列已排序，

我們可以選先最左與最右邊的元素來比較，把最大的元素，放在結果陣列裡，

接下來，不包含先前已比完的元素，

繼續選先最左與最右邊的元素來比較，把最大的元素，放在結果陣列裡，

直到選完為止，這個解法的時間複雜度為 O(n)。