977-Sorted squared array

tags: Easy

Question

https://leetcode.com/problems/squares-of-a-sorted-array/

Solution

• 一般寫法：平方再排序，因排序，故O(nlogn) time，in-place(沒用到額外記憶體空間)

#include <vector>
using namespace std;

vector<int> sortedSquaredArray(vector<int> array) {
  // Write your code here.
  // std::sort is O(nlogn) time
  for (auto &x: array){
      x *= x;
  }
  sort(array.begin(), array.end());
  return array;
}

• 時間較優解：由於平方最大出現在兩側，利用tow pointer從兩側開始比較再填值，雖然速度較快，但多用一個陣列的記憶體，O(n) time & space.

#include <vector>
using namespace std;

vector<int> sortedSquaredArray(vector<int> array) {
  // Write your code here.
  vector<int> squaredArray(array.size(), 0);
  int endIdx = array.size() - 1;
  int startIdx = 0;
  for (int i = array.size() - 1; i >= 0; i--){
      if (abs(array[endIdx]) >= abs(array[startIdx])){
          squaredArray[i] = array[endIdx]*array[endIdx];
          endIdx--;
      }else{
          squaredArray[i] = array[startIdx]*array[startIdx];
          startIdx++;
      }
  }
  return squaredArray;
}