判断能否形成等差数列

难度：⭐

题目描述：

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为等差数列。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例1：

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。

示例2：

输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

提示：

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

🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️

解题过程：

思路：

很简单，对数组升序排序，计算前两项的差d，然后从第3个元素遍历数组判断每一个元素与前一个元素之差是否等于d，如果不等于就不是等差数列返回false，循环结束证明是等差数列返回true。

c++代码：(执行用时4ms，击败98.95%，内存消耗9.1M，击败29.94%）

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {

        sort(arr.begin(),arr.end());
        //前两项的差
        int d=arr[1]-arr[0];
        int n=arr.size();
        for(int i=2;i<n;++i){
            if(arr[i]-arr[i-1]!=d){
                return false;
            }
        }
        return true;
    }
};

💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官方题解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎

官方题解:

方法一：模拟

思路与算法

首先我们对原序列排序，假设排序之后序列为 ${a_{0}, a_{1}, \dots a_{n}}$ ，如果对 $i \in [1, n - 1]$ 中的每个数都有 $a_{i} \times 2 = a_{i - 1} + a_{i + 1}$ 成立，那么这个数列就是等差数列。

c++代码：(执行用时8ms，击败86.14%，内存消耗9.2M，击败10.75%）

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        for (int i = 1; i < arr.size() - 1; ++i) {
            if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
};

复杂度分析

时间复杂度： $O (n \log n)$ 。排序的时间代价为 $O (n \log n)$ ，遍历序列的时间代价是 $O (n)$ ，故渐进时间复杂度为 $O (n \log n + n) = O (n \log n)$ 。
空间复杂度： $O (\log n)$ 。快速排序中使用的栈空间期望是 $O (\log n)$ 。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳

总结：

官方题解使用了等差数列的性质进行的判断，我是基于等差数列的性质判断的，都差不多，也比较简单。