[LeetCode] 360. Sort Transformed Array 排序转换后的数组

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 360. Sort Transformed Array 排序转换后的数组,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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.html

The returned array must be in sorted order.java

Expected time complexity: O(n)python

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]

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.函数

解法1:把每个数带入方程计算结果,而后对结果排序。Time: O(nlogn),不是题目想要的post

解法2:根据抛物线方程式的特色,a>0则抛物线开口朝上,两端的值比中间的大,a<0则抛物线开口朝下,则两端的值比中间的小,a=0时,则为直线方法,是单调递增或递减的。同时由于给定数组nums是有序的,因此才有O(n)的解法。this

当a>0,两端的值比中间的大,从后边往中间填数,用两个指针分别指向数组的开头和结尾,比较两个数,将其中较大的数存入res,而后该指针向中间移,重复比较过程,直到把res都填满。url

当a<0,两端的值比中间的小,从前边往中间填数,用两个指针分别指向数组的开头和结尾,比较两个数,将其中较小的数存入res,而后该指针向中间移,重复比较过程,直到把res都填满。指针

当a=0,函数是单调递增或递减的,那么从前日后填和从后往前填均可以,也能够将这种状况和a>0合并。code

Java:

public class Solution {    
    private int calcu(int x, int a, int b, int c){
        return a*x*x + b*x + c;
    }
    
    
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int index;
        if(a > 0){
            index = nums.length - 1 ;
        } else {
            index = 0;
        }
        int result[] = new int[nums.length];
        int i = 0;
        int j = nums.length - 1;
        if(a > 0){
            while(i <= j){
                result[index--] = calcu(nums[i],a,b,c) > calcu(nums[j],a,b,c) ? calcu(nums[i++],a,b,c):calcu(nums[j--],a,b,c);
            }
        }else{
            while(i <= j){
                result[index++] = calcu(nums[i],a,b,c) < calcu(nums[j],a,b,c) ? calcu(nums[i++],a,b,c):calcu(nums[j--],a,b,c);
            }  
        }
        return result;
    }
}  

Python: wo

class Solution():
    def sortTransformedArray(self, nums, a, b, c):
        if not nums:
            return []
        res = [0] * len(nums)
        i, j = 0, len(nums) - 1
        index = len(nums) - 1 if a >= 0 else 0
        while i <= j:
            if a >= 0:
                calc_i = self.calc(nums[i], a, b, c)
                calc_j = self.calc(nums[j], a, b, c)
                if  calc_i >= calc_j:
                    res[index] = calc_i
                    i += 1
                else:
                    res[index] = calc_j
                    j -= 1
                index -= 1
            else:
                calc_i = self.calc(nums[i], a, b, c)
                calc_j = self.calc(nums[j], a, b, c)
                if  calc_i <= calc_j:
                    res[index] = calc_i
                    i += 1
                else:
                    res[index] = calc_j
                    j -= 1
                index += 1

        return res

    def calc(self, x, a, b, c):
        return  a * x * x + b * x + c


if __name__ == '__main__':
    print Solution().sortTransformedArray([], 1, 3, 5)
    print Solution().sortTransformedArray([2], 1, 3, 5)
    print Solution().sortTransformedArray([-4, -2, 2, 4], 1, 3, 5)
    print Solution().sortTransformedArray([-4, -2, 2, 4], -1, 3, 5)
    print Solution().sortTransformedArray([-4, -2, 2, 4], 0, 3, 5)

C++:

class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size(), i = 0, j = n - 1;
        vector<int> res(n);
        int idx = a >= 0 ? n - 1 : 0;
        while (i <= j) {
            if (a >= 0) {
                res[idx--] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[i++], a, b, c) : cal(nums[j--], a, b, c);
            } else {
                res[idx++] = cal(nums[i], a, b, c) >= cal(nums[j], a, b, c) ? cal(nums[j--], a, b, c) : cal(nums[i++], a, b, c);
            }
        }
        return res;
    }
    int cal(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}; 

C++:

class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        if(nums.size() ==0) return {};
        vector<int> result;
        int left = 0, right = nums.size()-1;
        auto func = [=](int x) { return a*x*x + b*x + c; };
        while(left <= right)
        {
            int val1 = func(nums[left]), val2 = func(nums[right]);
            if(a > 0) result.push_back(val1>=val2?val1:val2);
            if(a > 0) val1>val2?left++:right--;
            if(a <= 0) result.push_back(val1>=val2?val2:val1);
            if(a <= 0) val1>val2?right--:left++;
        }
        if(a > 0) reverse(result.begin(), result.end());
        return result;
    }
};

  

  

 

All LeetCode Questions List 题目汇总