1502. 判断能否形成等差数列
难度简单给你一个数字数组 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
我的思路:
等差数列要么是递增 要么是递减 所以需要先排序。再判断两两相邻两数的差。
判断能否形成等差数列
力扣官方题解发布于 2020-07-121.7k官方C#C++JavaPython模拟方法一:模拟
思路与算法
首先我们对原序列排序,假设排序之后序列为 \{ a_0, a_1, \cdots a_n \}{a0,a1,⋯an},如果对 i \in [1, n - 1]i∈[1,n−1] 中的每个数都有 a_i \times 2 = a_{i - 1} + a_{i + 1}ai×2=ai−1+ai+1 成立,那么这个数列就是等差数列。
代码
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(nlogn)。排序的时间代价为 O(n \log n)O(nlogn),遍历序列的时间代价是 O(n)O(n),故渐进时间复杂度为 O(n \log n + n) = O(n \log n)O(nlogn+n)=O(nlogn)。
- 空间复杂度:O(\log n)O(logn)。快速排序中使用的栈空间期望是 O(\log n)O(logn)。