Mind palace

some thoughts

0%

360. Sort Transformed Array

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

O(n) time O(1) space
双指针
如果抛物线parabola开口朝上（a > 0）则取较大的那个数从后往前放
如果抛物线开口朝下（a < 0）则取较小的那个数从前往后放
可以看做977. Squares of a Sorted Array的followup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size(), l = 0, r = n - 1, i = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        auto f = [a, b, c](int x) { return (a * x + b) * x + c; };
        while (l <= r) { // 注意这里必须是l <= r因为l和r相遇时的那个数也要处理
            int fl = f(nums[l]), fr = f(nums[r]), mn = min(fl, fr), mx = max(fl, fr);
            if (a < 0) {
                res[i++] = mn;
                mn == fl ? ++l : --r;
            } else {
                res[i--] = mx;
                mx == fl ? ++l : --r;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size(), l = 0, r = n - 1, i = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        auto f = [a, b, c](int x) { return (a * x + b) * x + c; };
        while (l <= r) {
            int fl = f(nums[l]), fr = f(nums[r]);
            if (fl > fr) {
                if (a < 0) {
                    res[i++] = fr;
                    --r;
                } else {
                    res[i--] = fl;
                    ++l;
                }
            } else {
                if (a < 0) {
                    res[i++] = fl;
                    ++l;
                } else {
                    res[i--] = fr;
                    --r;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int t = -b;
        int n = nums.size(), l = 0, r = n - 1, i = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        while (l <= r) {
            int s = a * (nums[l] + nums[r]);
            if (s < t) {
                if (a < 0) {
                    res[i++] = nums[r--];
                } else {
                    res[i--] = nums[l++];
                }
            } else {
                if (a < 0) {
                    res[i++] = nums[l++];
                } else {
                    res[i--] = nums[r--];
                }
            }
        }
        for (int &x : res) {
            x = (a * x + b) * x + c;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        this->a = a;
        this->b = b;
        this->c = c;
        int t = -b;
        int n = nums.size(), l = 0, r = n - 1, i = a < 0 ? 0 : n - 1;
        vector<int> res(n);
        while (l <= r) {
            int s = a * (nums[l] + nums[r]);
            if (s < t) {
                if (a < 0) {
                    res[i++] = f(nums[r--]);
                } else {
                    res[i--] = f(nums[l++]);
                }
            } else {
                if (a < 0) {
                    res[i++] = f(nums[l++]);
                } else {
                    res[i--] = f(nums[r--]);
                }
            }
        }
        return res;
    }

    int f(int x) {
        return a * x * x + b * x + c;
    }

    int a, b, c;
};