1502.Can Make Arithmetic Progression From Sequence

Tags: Easy Array Sort

Links: https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/

---

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

---

判断数组中的数字重新排列能否组成等差数列，排序后看相邻两项之间的差值是否相等。时间复杂度$o(n \log n)$

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        sort(arr.begin(), arr.end());
        int n = arr.size();
        int gap = arr[1] - arr[0];
        for (int i = 2; i < n; ++i) {
            if (arr[i] - arr[i - 1] != gap) return false;
        }

        return true;
    }
};