0360 added.

liuyubobobo · liuyubobobo · commit 4a76d3e56c00 · 2018-08-13T03:11:56.000-07:00
diff --git a/0360-Sort-Transformed-Array/cpp-0360/CMakeLists.txt b/0360-Sort-Transformed-Array/cpp-0360/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(cpp_Sort_Transformed_Array)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(cpp_Sort_Transformed_Array ${SOURCE_FILES})
diff --git a/0360-Sort-Transformed-Array/cpp-0360/main.cpp b/0360-Sort-Transformed-Array/cpp-0360/main.cpp
@@ -0,0 +1,110 @@
+/// Source : https://leetcode.com/problems/sort-transformed-array/description/
+/// Author : liuyubobobo
+/// Time   : 2016-12-26
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+#include <cmath>
+
+using namespace std;
+
+
+/// Mathematics
+/// Based on the middle axis -b/(2a) to get the proper order of the transformation
+/// Need to pay attention when a == 0
+///
+/// Time Complexity:  O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    vector<int> sortTransformedArray(const vector<int>& nums, int a, int b, int c) {
+
+        vector<int> res;
+
+        if(a == 0){
+            // If a == 0, the result of the transform is linear
+            for(int i = 0 ; i < nums.size() ; i ++)
+                res.push_back(applyTransform(nums[i], a, b, c));
+
+            // If b < 0, we need to reverse the result to make the res be sorted
+            // from small elements to large elements
+            if(b < 0)
+                reverseArray(res);
+        }
+        else{
+            // If a != 0, we need to find the middle axis first
+            // which can be calculated as - b / 2*a
+            double m = - double(b) / double(2 * a);
+            //cout<<"m = "<<m<<endl;
+
+            // Then, find the first element index which is larger or equal than m
+            int r = bsearch(nums, m);
+            int l = r - 1;
+            //cout<<"l = "<<l<<" , r = "<<r<<endl;
+
+            // Similar to merge process,
+            // we use the two pointers tecnique to make the transform in order
+            while(l >= 0 || r < nums.size()){
+                if(l == -1)
+                    res.push_back(applyTransform(nums[r++], a, b, c));
+                else if(r == nums.size())
+                    res.push_back(applyTransform(nums[l--], a, b, c));
+                else if(m - double(nums[l]) <= double(nums[r]) - m)
+                    res.push_back(applyTransform(nums[l--], a, b, c));
+                else // m - double(nums[l]) > double(nums[r]) - m
+                    res.push_back(applyTransform(nums[r++], a, b, c));
+            }
+
+            // If a < 0, we need to reverse the result to make the res be sorted
+            if(a < 0)
+                reverseArray(res);
+        }
+
+        return res;
+    }
+
+private:
+    int applyTransform(int x, int a, int b, int c){
+        return a * x * x + b * x + c;
+    }
+
+    void reverseArray(vector<int> &v){
+        int i = 0, j = v.size() - 1;
+        while(i < j)
+            swap(v[i ++] , v[j --]);
+        return;
+    }
+
+    // Find the index of first element >= target
+    int bsearch(const vector<int> &vec, double target){
+
+        int l = 0, r = vec.size();
+        while(l < r){
+            int m = l + (r - l) / 2;
+            if(vec[m] < target)
+                l = m + 1;
+            else // vec[m] >= target
+                r = m;
+        }
+
+        assert(l == r);
+        return r;
+    }
+};
+
+
+void print_vec(const vector<int>& vec){
+    for(int e: vec)
+        cout << e << " ";
+    cout << endl;
+}
+
+int main() {
+
+    vector<int> nums = {-4, -2, 2, 4};
+    print_vec(Solution().sortTransformedArray(nums, 1, 3, 5));
+    print_vec(Solution().sortTransformedArray(nums, -1, 3, 5));
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -234,6 +234,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 349 | [Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/description/) | [无] | [C++](0349-Intersection-of-Two-Arrays/cpp-0349/) | [Java](0349-Intersection-of-Two-Arrays/java-0349/src/) | |
 | 350 | [Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/description/) | [无] | [C++](0350-Intersection-of-Two-Arrays-II/cpp-0350/) | [Java](0350-Intersection-of-Two-Arrays-II/java-0350/src/) | |
 | | | | | | |
+| 360 | [Sort Transformed Array](https://leetcode.com/problems/sort-transformed-array/description/) | [无] | [C++](0360-Sort-Transformed-Array/cpp-0360/) | | |
+| | | | | | |
 | 370 | [Range Addition](https://leetcode.com/problems/range-addition/description/) | | [C++](0370-Range-Addition/cpp-0370/) | | |
 | | | | | | |
 | 374 | [Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/description/) | [solution](https://leetcode.com/problems/guess-number-higher-or-lower/solution/) | [C++](0374-Guess-Number-Higher-or-Lower/cpp-0374/) | | |
