[977. Squares of a Sorted Array]
[(https://leetcode.cn/problems/squares-of-a-sorted-array/)
暴力解法
-
對陣列中每個元素平方后再排序
-
代碼如下：
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) { nums[i] *= nums[i]; } sort(nums.begin(), nums.end()); return nums; } }; -
時間復雜度： O(n + nlogn)
空間復雜度：O（1）
雙指標
-
根據題意，陣列內元素是按non-decreasing排列，因此，最大數必然要么在左要么在右，不可能在中間
-
故，我們設定 l = 0， r = nums.size() - 1 ，讓i指向起始位置，而r指向最終位置，兩邊不斷向中間移動
-
再者，我們創建一個與nums大小相同的新陣列，讓i指向陣列的最終位置
-
若nums[ l ] * nums[ l ] < nums[ r ] * nums[ r ]，result[ i-- ] = nums[ r ] * nums[ r ]
若nums[ l ] * nums[ l ] > nums[ r ] * nums[ r ]，result[ i-- ] = nums[ l ] * nums[ l ]
-
代碼如下：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = nums.size() - 1;
vector<int>result( i + 1 );
for( int l = 0, r = nums.size() - 1; l <= r; ) //最后需處理一個元素，因此為l <= r
{
if( nums[l] * nums[l] < nums[r] * nums[r] )
{
result[i--] = nums[r] * nums[r];
--r;
}
else
{
result[i--] = nums[l] * nums[l];
++l;
}
}
return result;
}
};
-
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513680.html
標籤：其他