C++でソート後の配列における隣接要素の最大差を求める方法

問題の概要

整数型の配列が与えられます。この配列は必ずしもソートされているとは限りません。求めたいのは、ソート後の配列において隣接する要素同士の差の最大値です。

解決の手順はシンプルです。まず配列を昇順(または降順)にソートし、その後、配列を先頭から走査しながら隣接要素間の差 Arr[i+1] - Arr[i] を計算します。各ステップで、その差がこれまでに見つかった最大値より大きければ、最大値を更新していきます。

入出力例

例1

入力: Arr[] = [1, 5, 10, 2, 7]

出力: ソート後の配列における隣接要素の最大差は 3

解説: 昇順にソートすると Arr[] = [1, 2, 5, 7, 10] となります。隣接要素間の差は以下の通りです。

Arr[1]-Arr[0]=1, 最大差=1
Arr[2]-Arr[1]=3, 最大差=3
Arr[3]-Arr[2]=2, 最大差=3
Arr[4]-Arr[3]=3, 最大差=3

例2

入力: Arr[] = [5, 11, 21, 15, 20]

出力: ソート後の配列における隣接要素の最大差は 6

解説: 昇順にソートすると Arr[] = [5, 11, 15, 20, 21] となります。隣接要素間の差は以下の通りです。

Arr[1]-Arr[0]=6, 最大差=6
Arr[2]-Arr[1]=4, 最大差=6
Arr[3]-Arr[2]=5, 最大差=6
Arr[4]-Arr[3]=1, 最大差=6

アルゴリズムの流れ

• 整数型の配列 Arr[] を入力として受け取ります。

• 配列を昇順にソートします(降順でも結果は変わりません)。

• これまでに見つかった最大差を格納する変数 MaxD を宣言し、初期値として Arr[1] - Arr[0] を設定します。

• 配列の2番目の要素から最後から2番目の要素までループ処理を行います。

• 計算した差 Arr[i+1] - Arr[i] が MaxD より大きい場合、MaxD を更新します。

• 最後から2番目の要素に達するまでこの処理を繰り返します。

• 結果として得られた MaxD を最大隣接差として出力します。

C++による実装例

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

int max_adj_Diff(int A[], int size){
    int MaxD = A[1] - A[0];
    for(int i = 1; i < size - 1; i++){
        if(A[i+1] - A[i] > MaxD)
            MaxD = A[i+1] - A[i];
    }
    return MaxD;
}

int main(){
    int Arr[] = {1, 5, 2, 18, 20, 13};
    int n = sizeof(Arr) / sizeof(Arr[0]);
    sort(Arr, Arr + n); // 配列を昇順にソート
    int md = max_adj_Diff(Arr, n);
    cout << "ソート後の配列における隣接要素の最大差 : " << md;
    return 0;
}

実行結果

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

ソート後の配列における隣接要素の最大差: 8

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。ソート後の走査は配列を一度通過するだけなので O(n) で済みます。また、追加のメモリは最大差を保持する変数のみであるため、空間計算量は O(1) となります。