【C++】ソート済み配列の各要素を2乗して昇順に出力する方法

問題概要

昇順にソートされた整数配列が与えられたとき、各要素を2乗した値を求め、その結果を再びソート順に出力するのが本記事の課題です。一見単純な処理ですが、負の数が含まれるため、単純に2乗するだけでは結果が昇順にならない点がポイントになります。

入力例1 −

arr[ ] = { -3,-1,0,1,4,6 };

出力 −

{0, 1, 1, 9, 16, 36}

説明 − 与えられた配列 [-3, -1, 0, 1, 4, 6] の各要素を2乗すると [9, 1, 0, 1, 16, 36] となります。これを昇順に並べ替えると [0, 1, 1, 9, 16, 36] になります。

入力例2 −

arr[ ] = { 0,1,2,8,9 }

出力 −

{0, 1, 4, 64, 81}

説明 − 配列 [0, 1, 2, 8, 9] の各要素を2乗すると [0, 1, 4, 64, 81] となり、この場合はすでに昇順に並んでいます。

この問題の解き方：Two-Pointer（双ポインタ）アプローチ

この問題は「Two-Pointer（双ポインタ）」という手法を使うことで効率的に解けます。Two-Pointerでは、left（左）とright（右）の2つのポインタを使用します。leftポインタは配列の先頭要素を、rightポインタは末尾要素を指すように初期化します。

配列を走査しながら各値の2乗を計算し、左端の要素の2乗と右端の要素の2乗の大小を比較していきます。元の配列がソートされているため、絶対値が最も大きい要素は必ず配列のどちらかの端に存在します。その性質を利用して、大きい方の2乗から順に結果を格納し、最後に反転させることで昇順の配列が完成します。

• 昇順に並んだ整数の配列を入力として受け取ります。

• 関数 squareAndSort(int *arr, int n) は、整数配列を引数に取り、各要素の2乗をソート済みの状態で返します。

• 2つのポインタ left と right を、それぞれ配列の先頭要素と末尾要素で初期化します。

• left 側と right 側の要素それぞれの2乗を計算し、大きい方を結果の配列に追加します。

• 比較結果に応じて、left ポインタを右へ、または right ポインタを左へ移動させます。

• left が right を追い越すまで繰り返し、最後に結果を反転して昇順にします。

実装例

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

vector<int> squareAndSort(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    vector<int> vec;

    while (left <= right) {
        int v1 = arr[left] * arr[left];
        int v2 = arr[right] * arr[right];

        if (v1 <= v2) {
            vec.push_back(v2);
            right--;
        } else {
            vec.push_back(v1);
            left++;
        }
    }

    reverse(vec.begin(), vec.end());
    return vec;
}

int main() {
    vector<int> arr = {-3, -1, 0, 1, 4, 6};
    vector<int> ans = squareAndSort(arr);

    for (auto x : ans) {
        cout << x << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

0 1 1 9 16 36

配列の各要素を2乗すると 9, 1, 0, 1, 16, 36 となります。これらを昇順にソートすると、出力は「0 1 1 9 16 36」になります。

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。すべての要素を2乗してから sort() 関数で並べ替える素朴な方法（O(n log n)）と比べて効率的であり、特に大規模な配列を扱う場合に有利です。空間計算量も結果を格納する分の O(n) で抑えられています。