LeetCode 360 - Sort Transformed Array


http://www.cnblogs.com/grandyang/p/5595614.html
Given a sorted array of integers nums and integer values ab and c. Apply a function of the form f(x) = ax2 +bx + c to each element x in the array.
The returned array must be in sorted order.
Expected time complexity: O(n)
Example:
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

这道题给了我们一个数组,又给了我们一个抛物线的三个系数,让我们求带入抛物线方程后求出的数组成的有序数组。那么我们首先来看O(nlgn)的解法,这个解法没啥可说的,就是每个算出来再排序,这里我们用了最小堆来帮助我们排序
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        vector<int> res;
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto d : nums) {
            q.push(a * d * d + b * d + c);
        }
        while (!q.empty()) {
            res.push_back(q.top()); q.pop();
        }
        return res;
    }

https://discuss.leetcode.com/topic/50373/simple-java-solution-using-priority-queue

    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i = 0;i<nums.length;i++){
            nums[i] = (a*nums[i]*nums[i]) + (b*nums[i]) + c;
            q.offer(nums[i]);
        }
        int i = 0;
        while(!q.isEmpty()){
            nums[i++] = q.poll();
        }
        return nums;
    }
但是题目中的要求让我们在O(n)中实现,那么我们只能另辟蹊径。其实这道题用到了大量的高中所学的关于抛物线的数学知识,我们知道,对于一个方程f(x) = ax2 + bx + c 来说,如果a>0,则抛物线开口朝上,那么两端的值比中间的大,而如果a<0,则抛物线开口朝下,则两端的值比中间的小。而当a=0时,则为直线方法,是单调递增或递减的。那么我们可以利用这个性质来解题,题目中说明了给定数组nums是有序的,如果不是有序的,我想很难有O(n)的解法。正因为输入数组是有序的,我们可以根据a来分情况讨论:
当a>0,说明两端的值比中间的值大,那么此时我们从结果res后往前填数,用两个指针分别指向nums数组的开头和结尾,指向的两个数就是抛物线两端的数,将它们之中较大的数先存入res的末尾,然后指针向中间移,重复比较过程,直到把res都填满。
当a<0,说明两端的值比中间的小,那么我们从res的前面往后填,用两个指针分别指向nums数组的开头和结尾,指向的两个数就是抛物线两端的数,将它们之中较小的数先存入res的开头,然后指针向中间移,重复比较过程,直到把res都填满。
当a=0,函数是单调递增或递减的,那么从前往后填和从后往前填都可以,我们可以将这种情况和a>0合并。
X. http://www.voidcn.com/article/p-qpohjolr-c.html
//还是数学解法,根据这个方程图形的特征来判断最大最小值的取向
    public int function(int num, int a, int b, int c) {
        return a * num * num + b * num + c; 
    }
    
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int len = nums.length;
        int[] result = new int[len];
        int index = a >= 0 ? len - 1 : 0;
        int i = 0, j = len - 1;
        while (i <= j) {
            if (a >= 0) {
                result[index--] = function(nums[i], a, b, c) >= function(nums[j], a, b, c) ? function(nums[i++], a, b, c) : function(nums[j--], a, b, c);
            } else {
                result[index++] = function(nums[i], a, b, c) <= function(nums[j], a, b, c) ? function(nums[i++], a, b, c) : function(nums[j--], a, b, c);
            }
        }
        return result;
    }
https://blog.csdn.net/qq508618087/article/details/51700774
思路: 当a>0时,抛物线开口向上,这样给定的数组最大值肯定是在两端, 也就是要么在数组开始,要么在数组的最后, 这样我们可以依次取得最大值.最后的时候翻转一下数组即可.
当a<0时, 抛物线开口向下,这样最小值肯定也是在两端, 我们可以依次在两端取最小值
https://segmentfault.com/a/1190000005771017
抛物线中点: -b/2a
分这么几种情况:
a > 0,
a < 0,
a == 0 && b >= 0,
a == 0 && b < 0
给的x数组是排序的,搞两个指针从两边比较
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] result = new int[nums.length];
        int start = 0, end = nums.length - 1;
        int nextIndex = 0;
        if (a > 0 || (a == 0 && b >= 0)) 
            nextIndex = nums.length - 1;
        if (a < 0 || (a == 0 && b < 0))
            nextIndex = 0;
        double mid = -1 * ((b * 1.0)  / (2.0 * a));
        while (start <= end) {
            if (a > 0 || (a == 0 && b >= 0)) {
                if (Math.abs(mid - nums[start]) > Math.abs(nums[end] - mid)) {
                    int x = nums[start++];
                    result[nextIndex--] = a * x * x + b * x + c;
                }
                else {
                    int x = nums[end--];
                    result[nextIndex--] = a * x * x + b * x + c;
                }
            }
            else if (a < 0 || (a == 0 && b < 0)){
                if (Math.abs(mid - nums[start]) > Math.abs(nums[end] - mid)) {
                    int x = nums[start++];
                    result[nextIndex++] = a * x * x + b * x + c;
                }
                else {
                    int x = nums[end--];
                    result[nextIndex++] = a * x * x + b * x + c;
                }
            }
        }
        return result;
    }
https://discuss.leetcode.com/topic/50497/my-easy-to-understand-java-ac-solution-using-two-pointers
For a parabola,
if a >= 0, the min value is at its vertex. So our our sorting should goes from two end points towards the vertex, high to low.
if a < 0, the max value is at its vertex. So our sort goes the opposite way.
http://juneend.blogspot.com/2016/07/360-sort-transformed-array.html
If a >=0, the minimum value is at the array's vertex. So we need to move the two end pointers toward the vertex and output from right to left.
If a <0, the maximum value is at the array's vertex. So we need to move the two end pointers toward the vertex but output from left to right.
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] res = new int[nums.length];
        int start = 0;
        int end = nums.length - 1;
        int i = a >= 0 ? nums.length - 1 : 0;
        while(start <= end) {
            int startNum = getNum(nums[start], a, b, c);
            int endNum = getNum(nums[end], a, b, c);
            if(a >= 0) {
                if(startNum >= endNum) {
                    res[i--] = startNum;
                    start++;
                }
                else{
                    res[i--] = endNum;
                    end--;
                }
            }
            else{
                if(startNum <= endNum) {
                    res[i++] = startNum;
                    start++;
                }
                else{
                    res[i++] = endNum;
                    end--;
                }
            }
        }
        return res;
    }
    public int getNum(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
https://leetcode.com/discuss/108831/java-o-n-incredibly-short-yet-easy-to-understand-ac-solution
the problem seems to have many cases a>0, a=0,a<0, (when a=0, b>0, b<0). However, they can be combined into just 2 cases: a>0 or a<0
1.a>0, two ends in original array are bigger than center if you learned middle school math before.
2.a<0, center is bigger than two ends.
so use two pointers i, j and do a merge-sort like process. depending on sign of a, you may want to start from the beginning or end of the transformed array. For a==0 case, it does not matter what b's sign is. The function is monotonically increasing or decreasing. you can start with either beginning or end.
public int[] sortTransformedArray(int[] nums, int a, int b, int c) { int n = nums.length; int[] sorted = new int[n]; int i = 0, j = n - 1; int index = a >= 0 ? n - 1 : 0; while (i <= j) { if (a >= 0) { sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c); } else { sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c); } } return sorted; } private int quad(int x, int a, int b, int c) { return a * x * x + b * x + c; }

X. Merge sort
https://discuss.leetcode.com/topic/48487/share-my-simple-java-solution-similar-to-merge-sort
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int result[] = new int[nums.length];
    int i = 0, j = nums.length - 1;
    if(a > 0){
        int index = result.length - 1;
        while(i <= j){
            int left = a*nums[i]*nums[i] + b*nums[i] + c;
            int right = a*nums[j]*nums[j] + b*nums[j] + c;
            if(left < right){
                result[index--] = right;
                j--;
            }
            else{
                result[index--] = left;
                i++;
            }
        }
    }
    else{
        int index = 0;
        while(i <= j){
            int left = a*nums[i]*nums[i] + b*nums[i] + c;
            int right = a*nums[j]*nums[j] + b*nums[j] + c;
            if(left < right){
                result[index++] = left;
                i++;
            }
            else{
                result[index++] = right;
                j--;
            }
        }
    }
    return result;
}
https://discuss.leetcode.com/topic/49462/7-line-and-9-line-concise-solutions-with-explanation
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        vector<int> res(nums.size()), y;
        for (auto &x: nums) y.emplace_back(a*x*x+b*x+c);

        int i = 0, j = nums.size()-1, k = a<0? 0: nums.size()-1;
        for(; i <= j; k += a<0? 1: -1) {
            if (y[i] < y[j] == a < 0) res[k] = y[i++];
            else                      res[k] = y[j--];
        }
        return res;
    }
X.
https://blog.csdn.net/magicbean2/article/details/77160524
这道题目的本质其实是对一个有序数组重新进行排序。由于是一个二次变换,所以分如下情况分别考虑:

1)a == 0:此时函数退化为线性函数,不用排序,直接变换并且返回(如果b < 0的时候需要对结果进行逆转)。

2)a != 0:此时首先计算出二次函数的对称轴(-b / (2 * a)),然后根据距离这个对称轴的远近对nums中的元素进行排序,再进行变换(当然在a < 0的情况下,还需要对变换结果进行逆转)。由于原来的数组已经是有序的了,所以这里的重新排序可以在O(n)的时间内完成。
https://discuss.leetcode.com/topic/48436/simple-and-concise-o-n-solution
ax2+bx+c = a(x + b/2a)2 + c - b2/4a
So use offset as c - b2/4a
ax2+bx+c - offset will be always positive or negative
Then iteratively pop max (or min if a is negative) from both ends and push it into final array
function sortTransformedArray(nums, a, b, c) {
    var arr = nums.map(n => a * n * n + b * n + c);
    var offset = a ? c - (b * b) / (4 * a) : Math.min(arr[0], arr.slice(-1)[0]);
    var res = [];

    for (var l = 0, r = arr.length - 1; l <= r;) {
        if (Math.abs(arr[l] - offset) >= Math.abs(arr[r] - offset)) {
            res.push(arr[l++]);
        } else {
            res.push(arr[r--]);
        }
    }

    return res[0] > res[res.length - 1] ? res.reverse() : res;
}
http://blog.csdn.net/jmspan/article/details/51698835

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts