C++で隣接する同じ要素を2倍にし、ゼロを配列の末尾へ移動する方法

このチュートリアルでは、配列内の隣接する同じ要素を2倍にし、すべてのゼロを配列の末尾へ移動するC++プログラムを作成します。

問題の概要

隣接するインデックスに同じ値が並んでいる場合、それらをペアとして扱い、数を2倍にします。2倍にした後は、余分となった要素をゼロに置き換え、最後に配列内のすべてのゼロを末尾へ移動させます。

具体的な処理の手順は以下の通りです。

1. 隣接する2つの要素が同じ非ゼロの値であれば、先頭側の要素を2倍にし、後ろ側の要素を0にします。
2. ペアとして処理した分はスキップし、次の要素へ進みます。
3. 最後に、ゼロ以外の要素を前方へ寄せ、残りの位置を0で埋めます。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            arr[count++] = arr[i];
        }
    }
    while (count < n) {
        arr[count++] = 0;
    }
}
void updateAndRearrangeArray(int arr[], int n) {
    if (n == 1) {
        return;
    }
    for (int i = 0; i < n - 1; i++) {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {
            arr[i] = 2 * arr[i];
            arr[i + 1] = 0;
            i++;
        }
    }
    moveZeroesToEnd(arr, n);
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main() {
    int arr[] = { 2, 3, 3, 4, 0, 5, 5, 0 }, n = 7;
    cout << "Given Array: ";
    printArray(arr, n);
    cout << endl;
    updateAndRearrangeArray(arr, n);
    cout << "Updated Array: ";
    printArray(arr, n);
    cout << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Given Array: 2 3 3 4 0 5 5
Updated Array: 2 6 4 10 0 0 0

コードのポイント

moveZeroesToEnd関数では、ゼロ以外の要素を順に前方へ詰めていき、残りの位置を0で埋めることで、計算量O(n)で効率よくゼロを末尾へ移動しています。

updateAndRearrangeArray関数では、隣接する同じ非ゼロ要素を検出すると、前者を2倍・後者を0に置き換えたうえでインデックスを1つ余分に進めることで、すでに処理済みの要素を誤って再度ペア化することを防いでいます。

まとめ

このように、配列を一度走査してペアとなる要素を2倍にした後、もう一度走査してゼロを末尾へ移動するだけで、目的の操作を線形時間で実現できます。本チュートリアルについてご不明な点がある場合は、コメント欄にてお気軽にお知らせください。