Easy

题目描述

如果一个数字序列中任意两个连续元素之间的差值都相同，那么这个序列就被称为等差数列。

给定一个数字数组 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

提示：

  • 任何有效的等差数列都是有序的
  • 对数组排序，然后检查所有连续元素的差值是否相等

解题思路

解题思路

这道题的核心思想是：等差数列在排序后，任意两个相邻元素的差值都相等。

方法一：排序 + 检查差值（推荐）

思路分析：

  1. 将数组排序，这样如果能构成等差数列，排序后的数组就是一个等差数列
  2. 计算排序后数组中相邻元素的差值
  3. 检查所有相邻元素的差值是否都相等

这种方法简单直观，时间复杂度主要由排序决定。

方法二：数学方法

还可以利用等差数列的数学性质：如果数组能构成等差数列，那么：

  • 公差 = (最大值 - 最小值) / (数组长度 - 1)
  • 且公差必须是整数
  • 排序后检查是否符合等差数列规律

但考虑到实现复杂度和可读性，方法一更加直观易懂。

时间复杂度： O(n log n)，主要是排序的复杂度 空间复杂度： O(1)，只使用常数额外空间

代码实现

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

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        
        diff = arr[1] - arr[0]
        for i in range(2, len(arr)):
            if arr[i] - arr[i-1] != diff:
                return False
        return True

public class Solution {
    public bool CanMakeArithmeticProgression(int[] arr) {
        Array.Sort(arr);
        
        int diff = arr[1] - arr[0];
        for (int i = 2; i < arr.Length; i++) {
            if (arr[i] - arr[i-1] != diff) {
                return false;
            }
        }
        return true;
    }
}

var canMakeArithmeticProgression = function(arr) {
    arr.sort((a, b) => a - b);
    
    const diff = arr[1] - arr[0];
    for (let i = 2; i < arr.length; i++) {
        if (arr[i] - arr[i-1] !== diff) {
            return false;
        }
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，遍历检查需要 O(n)
空间复杂度O(1)只使用常数额外空间（原地排序）

相关题目