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

1. Use swapsort:

  1. //TLE
  3. class Solution {
  4. public:
  5.     vector<int> sortedSquares(vector<int>& A) {
  6.         if(A.empty()) return A;
  8.         for(int i = 0; i < A.size() - 1; i++){
  9.             for(int j = i + 1; j < A.size(); j++){
  10.                 if(abs(A[i]) > abs(A[j]))
  11.                     swap(A[i], A[j]);
  12.             }
  13.         }
  15.         for(int i = 0; i < A.size(); i++)
  16.             A[i] = A[i] * A[i];
  18.         return A;
  19.     }
  20. };

2. Use STL template:

  1. //116 ms    25.9 MB
  3. class Solution {
  4. public:
  5.     vector<int> sortedSquares(vector<int>& A) {
  6.         if(A.empty()) return A;
  8.         for(int i = 0; i < A.size(); i++){
  9.             A[i] = A[i] * A[i];
  10.         }
  12.         sort(A.begin(), A.end());
  14.         return A;
  15.     }
  16. };

3. Use two pointers:

  1. //56 ms    26.8 MB
  3. class Solution {
  4. public:
  5.     vector<int> sortedSquares(vector<int>& A) {
  6.         if(A.empty()) return A;
  8.         int n = A.size();
  9.         int r = 0;
  11.         while(r < n && A[r] < 0)
  12.             r++;
  14.         int l = r - 1;
  16.         vector<int> result;
  18.         while(l>=0 && r<=n-1) {
  19.             if(abs(A[l]) < abs(A[r])){
  20.                 result.push_back(A[l]*A[l]);
  21.                 l--;
  22.             } else {
  23.                 result.push_back(A[r]*A[r]);
  24.                 r++;
  25.             }
  26.         }
  28.         while(l>=0){
  29.             result.push_back(A[l]*A[l]);
  30.             l--;
  31.         }       
  32.         while(r<=n-1){
  33.             result.push_back(A[r]*A[r]);
  34.             r++;
  35.         }
  37.         return result;
  38.     }
  39. };

4. Use MergeSort:

  1. //return vectors
  2. //512 ms    86.1 MB
  4. class Solution {
  5. public:
  6.     vector<int> sortedSquares(vector<int>& A) {
  7.         if(A.empty()) return A;
  9.         int n = A.size();
  11.         for(int i = 0; i < n; i++)
  12.             A[i] = A[i] * A[i];
  14.         vector<int> result = MergeSort(A, 0, A.size()-1);
  16.         return result; 
  17.     }
  19. private:
  20.     vector<int> Merge(vector<int>& L, vector<int>& R){
  21.         vector<int> sumup;
  23.         int l_index = 0;
  24.         int r_index = 0;
  26.         while(l_index < L.size() && r_index < R.size()) {
  27.             if(L[l_index] <= R[r_index]) {
  28.                 sumup.push_back(L[l_index]);
  29.                 l_index++;
  30.             } else {
  31.                 sumup.push_back(R[r_index]);
  32.                 r_index++;
  33.             }
  34.         }
  36.         while(l_index < L.size()){
  37.             sumup.push_back(L[l_index]);
  38.             l_index++;
  39.         }
  41.         while(r_index < R.size()){
  42.             sumup.push_back(R[r_index]);
  43.             r_index++;
  44.         }
  46.         return sumup;
  47.     }
  49.     vector<int> MergeSort(vector<int>& A, int l, int r){
  50.         if(l==r) return {A[l]};
  52.         int mid = l + (r - l) / 2;
  54.         vector<int> L = MergeSort(A, l, mid);
  55.         vector<int> R = MergeSort(A, mid + 1, r);
  57.         return Merge(L, R);
  58.     }
  59. };