给你一个数字数组 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
方法一：模拟
思路与算法
首先我们对原序列排序，假设排序之后序列为 { a_0, a_1, \cdots a_n \，如果对 i \in [1, n - 1] 中的每个数都有 a_i \times 2 = a_{i - 1} + a_{i + 1 成立，那么这个数列就是等差数列。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
| 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;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
for (int i = 1; i < arr.length - 1; ++i) {
if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {
return false;
}
}
return true;
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
| class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
arr.sort()
for i in range(1, len(arr) - 1):
if arr[i] * 2 != arr[i - 1] + arr[i + 1]:
return False
return True
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution
{
public bool CanMakeArithmeticProgression(int[] arr)
{
Array.Sort(arr);
for (int i = 1; i < arr.Length - 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)。
