LeetCode 1502. 判断能否形成等差数列
题目描述
原题：1502. 判断能否形成等差数列。
给定整数数组arr，判断能否重新排列为等差数列，返回布尔值。2≤n≤1000，元素在-10^6…10^6。这里采用进阶的O(n)时间解法，并使用O(1)额外空间，允许原地重排数组。
示例 1：
输入：arr = [3,5,1]
输出：true
解释：重新排列为 [1,3,5]，相邻元素之差均为 2。
示例 2：
输入：arr = [1,2,4]
输出：false
解释：无法重新排列成等差数列。
示例 3：
输入：arr = [7,7,7]
输出：true
解释：公差为 0，原数组已经是等差数列。
提示：
- 2≤n≤1000，元素在 -10^6…10^6。本节实现进一步要求 O(n) 时间、O(1) 额外空间，允许原地重排数组。
题意分析
判断数组能否重新排列为等差数列，即排列后任意相邻两项之差都相同。允许改变原顺序，只返回是否可行，不需要输出特定排列。
原题可以排序后检查，本篇采用题面中进一步约定的线性时间、常量额外空间做法。只需考虑升序等差排列：若能排成递减数列，反转后也能得到同样有效的递增数列；所有值相等则公差为零。
解法：按公差计算目标位置并原地归位
核心思路
[!blue]
设最小值为
low、最大值为high、长度为n。升序等差排列的首末项只能是这两个极值，中间有n - 1个间隔，因此公差只能为(high - low) / (n - 1)。跨度不能整除间隔数时，没有整数公差，直接失败。公差为零意味着最大值等于最小值，所有元素已经相同，直接成功。当公差
step > 0时，下标i的目标值唯一为low + i * step。任意元素value的目标位置也唯一为(value - low) / step，但前提是分子能够被公差整除。否则这个元素不属于目标等差序列，应立即返回假。由于所有值都在最小值和最大值之间，合法目标下标自然处于零到n - 1之间。从左到右检查每个位置。如果当前位置已经等于目标值，就继续下一位置；否则计算当前元素应该去的下标，并把它与目标位置交换。被换回来的元素也可能没有放对，所以仍停在当前下标，继续检查，直到当前位置正确。
交换前若目标位置已经有与当前元素相同的值，就出现重复占位。非零公差的目标序列每个值只需要一份，而当前下标仍不正确，说明这是另一个副本，没有第二个合法位置可放，因此返回假，也避免了相同值之间无限交换。
每次成功交换至少把一个元素放到它的最终位置。已经正确的位置不会再被错误元素换走：只有同一个目标值才会指向它，遇到重复时会提前结束。因此整个过程中成功归位的次数最多为线性数量，虽然有内层循环，总时间仍是 $O(n)$。
解题步骤
- 两个元素总能形成等差数列；其余情况先遍历求最小值和最大值。
- 检查跨度是否整除
n - 1，计算唯一公差；公差为零直接返回真。- 逐个检查目标位置，当前位置不正确时，计算当前值的差值及应去下标。
- 差值不能整除公差或目标位置已经被相同值占据时返回假，否则交换并继续处理当前下标。
- 全部位置归位后返回真。
代码实现
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
int n = arr.length;
if (n <= 2) {
return true;
}
long low = arr[0];
long high = arr[0];
for (int x : arr) {
low = Math.min(low, x);
high = Math.max(high, x);
}
long span = high - low;
if (span % (n - 1) != 0) {
return false;
}
long step = span / (n - 1);
if (step == 0) {
return true;
}
for (int i = 0; i < n; i++) {
while (arr[i] != low + i * step) {
long delta = arr[i] - low;
if (delta % step != 0) {
return false;
}
int target = (int) (delta / step);
if (arr[target] == arr[i]) {
return false;
}
int value = arr[target];
arr[target] = arr[i];
arr[i] = value;
}
}
return true;
}
}
func canMakeArithmeticProgression(arr []int) bool {
n := len(arr)
if n <= 2 {
return true
}
low, high := int64(arr[0]), int64(arr[0])
for _, x := range arr {
low = min(low, int64(x))
high = max(high, int64(x))
}
span := high - low
if span%int64(n-1) != 0 {
return false
}
step := span / int64(n-1)
if step == 0 {
return true
}
for i := 0; i < n; i++ {
for int64(arr[i]) != low+int64(i)*step {
delta := int64(arr[i]) - low
if delta%step != 0 {
return false
}
target := int(delta / step)
if arr[target] == arr[i] {
return false
}
arr[target], arr[i] = arr[i], arr[target]
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n)$。极值扫描和外层遍历为线性，所有成功交换合计也至多为线性数量。
- 空间复杂度：$O(1)$，只保存极值、公差、下标和交换临时值，直接在输入数组中归位。
关键点总结
[!green]
- 极值和长度唯一确定候选公差，每个值再由公差唯一确定目标位置。
- 整除检查保证值属于目标序列，重复占位检查保证每个目标位置只有一个元素。
- 内层循环处理换回的元素，每次交换都完成至少一个最终位置，因此不会退化为平方时间。
易错点总结
[!yellow]
- 未先处理零公差，就使用除法或取模，会出现除零。
- 未检查差值整除就直接算目标下标，会把本来不属于等差序列的值舍入到某个位置。
- 交换一次就推进外层下标，可能让换回来的错误元素留在原地。
- 缺少重复占位检查，非零公差下的重复值可能不断互换，无法结束。
- 当前函数会修改输入，即使最终返回假，前面完成的交换也不会自动恢复。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 41. 缺失的第一个正数 | 困难 | 同样把元素交换到由数值决定的目标位置；本题位置由最小值与公差决定，并检查重复占位。 |