LeetCode 1502. Can Make Arithmetic Progression From Sequence

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCode 1502. Can Make Arithmetic Progression From Sequence を解きました。

設問

与えられた配列が等差数列arithmetic progressionに並び変えられることができるかを返す問題。

解

前日の1232. Check If It Is a Straight Lineに類似しています。今回は差を求めるだけなのでより簡単です。

まず配列をソートします。そして、それぞれの要素の差を見て全て同じであればtrue、そうでなければfalseを返せば完成です。

std::sort関数の計算量はO(N logN)なので、全体の計算量はO(N logN)で、消費メモリは、O(1)です。

class Solution {
   public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        const auto n = arr.size();
        sort(arr.begin(), arr.end());

        auto diff0 = arr[1] - arr[0];
        for (size_t i = 2; i < n; i++) {
            if (diff0 != arr[i] - arr[i - 1]) {
                return false;
            }
        }

        return true;
    }
};