C++で二次関数変換後の配列を効率的にソートする方法

問題の概要

ソート済みの整数配列 nums と、3つの整数値 a、b、c が与えられます。配列内の各要素 x に対して二次関数 f(x) = ax² + bx + c を適用し、最終的な配列をソート済みの状態で返すことが求められます。

たとえば、入力が nums = [-4, -2, 2, 4]、a = 1、b = 3、c = 5 の場合、出力は [3, 9, 15, 33] となります。

アプローチ：二ポインタ法による O(n) の解法

この問題は、二次関数のグラフ（放物線）の性質を利用すると、追加のソート処理なしに線形時間 O(n) で解くことができます。鍵となるのは次の性質です。

• a ≥ 0 の場合（下に凸の放物線）： 最大値は必ず元の配列の両端のいずれかに現れます。したがって、結果配列の後ろから大きい値を埋めていきます。
• a < 0 の場合（上に凸の放物線）： 最小値は必ず元の配列の両端のいずれかに現れます。したがって、結果配列の前から小さい値を埋めていきます。

アルゴリズムの手順

1. 関数 f(x, a, b, c) を定義し、ax² + bx + c の計算結果を返します。
2. n を配列 nums のサイズとし、start = 0、end = n − 1 で初期化します。
3. サイズ n の結果配列 ret を用意します。
4. a ≥ 0 の場合： i を n−1 から 0 へ減らしながら、nums[start] と nums[end] の関数値 x、y を比較します。x > y なら start を進めて ret[i] = x、そうでなければ end を戻して ret[i] = y とします。
5. a < 0 の場合： i を 0 から n−1 へ増やしながら同様に比較し、x < y なら start を進めて ret[i] = x、そうでなければ end を戻して ret[i] = y とします。
6. 最後に ret を返します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    int f(int x, int a, int b, int c){
        return a * x * x + b * x + c;
    }
    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
        int n = nums.size();
        int start = 0;
        int end = n - 1;
        vector<int> ret(n);
        if (a >= 0) {
            for (int i = n - 1; i >= 0; i--) {
                int x = f(nums[start], a, b, c);
                int y = f(nums[end], a, b, c);
                if (x > y) {
                    start++;
                    ret[i] = x;
                }
                else {
                    ret[i] = y;
                    end--;
                }
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                int x = f(nums[start], a, b, c);
                int y = f(nums[end], a, b, c);
                if (x < y) {
                    start++;
                    ret[i] = x;
                }
                else {
                    ret[i] = y;
                    end--;
                }
            }
        }
        return ret;
    }
};

main(){
    Solution ob;
    vector<int> v = {-4,-2,2,4};
    print_vector(ob.sortTransformedArray(v, 1, 3, 5));
}

実行結果

入力

{-4,-2,2,4}, 1, 3, 5

出力

[3, 9, 15, 33]

計算量について

この手法では、配列を一度走査するだけなので時間計算量は O(n) です。また、結果を格納するための配列が必要なため、空間計算量も O(n) となります。単純に全要素へ関数を適用してからソートする方法（O(n log n)）と比べ、入力がソート済みであることを活かした効率的な解法といえます。