leetcode360-Sort Transform Array-locked (好题)

leetcode360-Sort Transform Array-locked (好题)

题目意思

这个题目是说,给定一个单调递增的数组,比如说[-10,1,4,9,34], 再给定一个函数ax^2+bx+c,其中a,b,c是给定的值,a可以为0, 那么数组中的每个数都经过这个函数之后就会得到一个新数组,现在是求将新数组从小到大排序并返回。

想法

最直观的想法是,先得到新的数组,再对数组排序,那么这样的话,先得到新的数组,是O(n)(假设重复的算多个),再排序,最快是O(nlogn),所以这样最快就是O(nlogn)了。

再进一步想的话,其实没必要非得等所有的数都算出来之后再排序,可以边算边排的,这时候要用到堆的办法了,具体应该是小顶堆,即每次算一个数,就把新算好的数放到其该在的位置上去。但是这样听上去似乎高效了些,但是也应该是O(nlogn)。

但是题目中的要求是用O(n)的时间复杂度就要返回结果,说明每个数就‘看’了一次。

其实上面的两个想法,并没有把这个函数考虑进去,实际上这个函数很关键,如果a等于0的话,就是个直线,只要看b的值就知道该怎么返回了,如果a大于0的话,此时任意拿三个从小到大的数,两端的函数值的最大值一定比中间的那个大,这样想的话,思路就有了。

具体可以每次取两个数,一个在前面,一个在后面,如果a大于0的话,就把二者函数值中的最大值放在当前数组的最后,然后最大值对应的那个向前或者向后移动,

具体用c++来写是下面的过程。

class Solution{

public:
    vector<int>sortTransformedArray(vector<int>& nums, int a, int b , int c){
        int n = nums.size();
        int i=0,j=n-1;   //一个是数组的开头,一个是结尾
        vector<int> res(n);

        int idx=a>=0?n-1:0;   //这个是判断a的值,来决定先放哪边
        
        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;
    }





}

然后刚才说的最小堆的实现如下

class Solution{
public:
    vector<int> sortTrandsformedArray(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;
    }
}

注意 priori_queue默认的比较方式是less<T>() 产生最大堆,反之,仿函数为greater<T>()产生最小堆。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦