1502. Can Make Arithmetic Progression From Sequence

题目信息

题号:

1502

难度:

Easy

主题:

数组、全排列、排序、等差数列、位置映射

原题:

LeetCode 1502

重点:

从枚举全部排列,推导到排序后的唯一候选,再利用最小值和最大值直接验证目标位置

题目重述

给定一个长度为 n 的整数数组 arr。可以任意调整元素顺序,但每个元素必须且只能使用一次。

判断是否存在一个重排后的数组 b 和一个固定整数 d,使所有 1 <= i < n 都满足:

b[i] - b[i - 1] = d

只需返回是否存在这样的排列,不需要返回具体排列。公差 d 可以为正数、负数或 0。

约束为 2 <= arr.length <= 1000、-10^6 <= arr[i] <= 10^6。

自建示例

输入:arr = [3,5,1]
输出:true

排序后得到 [1,3,5],相邻差都为 2。

输入:arr = [1,2,4]
输出:false

排序后相邻差分别为 1 和 2,不存在其他顺序能够形成等差数列。

输入:arr = [7,7,7]
输出:true

所有元素相同,公差为 0。

输入:arr = [1,1,3]
输出:false

跨度为 2,长度为 3,目标公差为 1;数值 2 缺失,而位置 0 被重复占用。

C++ 实现

#include <algorithm>
#include <vector>

class Solution {
private:
    bool isArithmetic(const std::vector<int>& nums) {
        const long long difference =
            static_cast<long long>(nums[1]) - nums[0];

        for (int i = 2; i < static_cast<int>(nums.size()); ++i) {
            const long long currentDifference =
                static_cast<long long>(nums[i]) - nums[i - 1];
            if (currentDifference != difference) return false;
        }
        return true;
    }

    bool enumeratePermutations(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        do {
            if (isArithmetic(nums)) return true;
        } while (std::next_permutation(nums.begin(), nums.end()));
        return false;
    }

    bool sortAndCheck(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        return isArithmetic(nums);
    }

    bool validatePositions(const std::vector<int>& nums) {
        const int n = static_cast<int>(nums.size());
        const auto [minimumIt, maximumIt] =
            std::minmax_element(nums.begin(), nums.end());

        const long long minimum = *minimumIt;
        const long long maximum = *maximumIt;
        const long long span = maximum - minimum;

        if (span == 0) return true;
        if (span % (n - 1) != 0) return false;

        const long long difference = span / (n - 1);
        std::vector<char> occupied(n, false);

        for (int value : nums) {
            const long long offset =
                static_cast<long long>(value) - minimum;
            if (offset % difference != 0) return false;

            const long long index = offset / difference;
            if (index < 0 || index >= n || occupied[index]) {
                return false;
            }
            occupied[index] = true;
        }
        return true;
    }

public:
    bool canMakeArithmeticProgression(std::vector<int>& arr) {
        return sortAndCheck(arr);
    }
};

题解

从全排列开始

题目允许任意重排,最直接的方法是枚举全部排列。对每个排列,用前两个元素确定公差,再检查后续相邻差。 只要一个排列通过检查即可返回 true。

enumeratePermutations 先排序,再用 next_permutation 按字典序生成所有不同排列。这个方法不会遗漏任何 可能顺序,但最多需要检查 n! 个排列,每次检查又需要 O(n) 时间,无法处理 n = 1000。

瓶颈不在相邻差检查,而在于尚未利用等差数列对顺序的限制。

有序候选

若某个合法排列的公差 d < 0,把排列反转后便得到公差 -d > 0 的合法排列。因此只要答案存在,就一定 存在一个公差非负的合法排列。

公差非负时,序列必然按非递减顺序排列。数组排序后恰好得到全部元素唯一的非递减顺序,所以所有排列候选可以 压缩为一个:

sort(arr)

排序结果是等差数列时,原数组显然可以重排成功;排序结果不是等差数列时,也不存在另一个非递减候选能够改变 相邻差。

相邻差不变量

设排序后的数组为 nums,第一对元素确定目标公差:

difference = nums[1] - nums[0]

扫描到下标 i 前,已经确认 nums[0..i-1] 的全部相邻差都等于 difference。当前只需检查:

nums[i] - nums[i-1] == difference

检查通过后,不变量扩展到 i;任意一次失败都说明排序后的唯一候选不合法,可以立即返回 false。

sortAndCheck 因而把阶乘级排列搜索降为一次排序和一次线性扫描。公开入口调用这一实现,因为代码短、状态少, 并且在题目规模下已经足够高效。按值接收副本也避免修改调用者传入的数组。

位置映射

还可以继续消除排序。长度为 n 的等差数列一旦确定最小值 minimum 和最大值 maximum,公差只能是:

difference = (maximum - minimum) / (n - 1)

若跨度不能被 n - 1 整除,就不存在整数公差。公差确定后,任意元素 value 的目标下标也唯一确定:

index = (value - minimum) / difference

因此 validatePositions 对每个元素检查三件事:偏移量能被公差整除、目标下标位于 [0,n-1]、目标位置 尚未被其他元素占用。全部元素都通过时,恰好填满等差数列的全部位置。

重复与零公差

当 maximum == minimum 时,所有元素相同,公差为 0,结果直接为 true。这一步必须在取模和除法前 处理,避免除以零。

当公差非零时,不同下标对应不同数值。若两个输入元素映射到同一个位置,说明出现了不允许的重复,同时必然有 另一个目标值缺失,立即返回 false。

排序方法通过不一致的相邻差发现同一问题;位置映射则通过整除失败或位置冲突发现问题。两种方法验证的是同一个 等差结构。

三种方法的关系

全排列方法不知道合法顺序,只能尝试所有候选。排序方法证明非递减顺序是唯一候选,删除了排列搜索。位置映射 进一步证明每个元素的目标位置都能直接计算,又删除了排序。

优化过程依次压缩的是:

全部排列 -> 唯一有序排列 -> 每个值的唯一目标位置

复杂度分析

enumeratePermutations 最坏检查 n! 个排列,每次检查 O(n),时间为 O(n! · n);排列数组副本 占用 O(n),排序调用栈通常为 O(log n)。

sortAndCheck 的排序时间为 O(n log n),扫描时间为 O(n);数组副本占用 O(n)。公开入口使用 这一实现,且不修改输入。

validatePositions 两次线性扫描即可完成验证,时间为 O(n),位置数组占用 O(n)。

边界处理

长度为 2 时,任意两个元素都能确定一个公差。所有元素相同时,排序方法自然通过,位置方法由 span == 0 直接返回。数组包含负数时,排序、跨度和位置关系均不改变。

差值与跨度使用 long long 计算,避免整数减法在更大数据范围下溢出。