1502. Can Make Arithmetic Progression From Sequence =================================================== 题目信息 -------- :题号: 1502 :难度: Easy :主题: 数组、全排列、排序、等差数列、位置映射 :原题: `LeetCode 1502 `_ :重点: 从枚举全部排列,推导到排序后的唯一候选,再利用最小值和最大值直接验证目标位置 题目重述 -------- 给定一个长度为 ``n`` 的整数数组 ``arr``。可以任意调整元素顺序,但每个元素必须且只能使用一次。 判断是否存在一个重排后的数组 ``b`` 和一个固定整数 ``d``,使所有 ``1 <= i < n`` 都满足: .. code-block:: text b[i] - b[i - 1] = d 只需返回是否存在这样的排列,不需要返回具体排列。公差 ``d`` 可以为正数、负数或 ``0``。 约束为 ``2 <= arr.length <= 1000``、``-10^6 <= arr[i] <= 10^6``。 自建示例 -------- .. code-block:: text 输入:arr = [3,5,1] 输出:true 排序后得到 ``[1,3,5]``,相邻差都为 ``2``。 .. code-block:: text 输入:arr = [1,2,4] 输出:false 排序后相邻差分别为 ``1`` 和 ``2``,不存在其他顺序能够形成等差数列。 .. code-block:: text 输入:arr = [7,7,7] 输出:true 所有元素相同,公差为 ``0``。 .. code-block:: text 输入:arr = [1,1,3] 输出:false 跨度为 ``2``,长度为 ``3``,目标公差为 ``1``;数值 ``2`` 缺失,而位置 ``0`` 被重复占用。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool isArithmetic(const std::vector& nums) { const long long difference = static_cast(nums[1]) - nums[0]; for (int i = 2; i < static_cast(nums.size()); ++i) { const long long currentDifference = static_cast(nums[i]) - nums[i - 1]; if (currentDifference != difference) return false; } return true; } bool enumeratePermutations(std::vector 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 nums) { std::sort(nums.begin(), nums.end()); return isArithmetic(nums); } bool validatePositions(const std::vector& nums) { const int n = static_cast(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 occupied(n, false); for (int value : nums) { const long long offset = static_cast(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& arr) { return sortAndCheck(arr); } }; 题解 ---- 从全排列开始 ~~~~~~~~~~~~ 题目允许任意重排,最直接的方法是枚举全部排列。对每个排列,用前两个元素确定公差,再检查后续相邻差。 只要一个排列通过检查即可返回 ``true``。 ``enumeratePermutations`` 先排序,再用 ``next_permutation`` 按字典序生成所有不同排列。这个方法不会遗漏任何 可能顺序,但最多需要检查 ``n!`` 个排列,每次检查又需要 ``O(n)`` 时间,无法处理 ``n = 1000``。 瓶颈不在相邻差检查,而在于尚未利用等差数列对顺序的限制。 有序候选 ~~~~~~~~ 若某个合法排列的公差 ``d < 0``,把排列反转后便得到公差 ``-d > 0`` 的合法排列。因此只要答案存在,就一定 存在一个公差非负的合法排列。 公差非负时,序列必然按非递减顺序排列。数组排序后恰好得到全部元素唯一的非递减顺序,所以所有排列候选可以 压缩为一个: .. code-block:: text sort(arr) 排序结果是等差数列时,原数组显然可以重排成功;排序结果不是等差数列时,也不存在另一个非递减候选能够改变 相邻差。 相邻差不变量 ~~~~~~~~~~~~ 设排序后的数组为 ``nums``,第一对元素确定目标公差: .. code-block:: text difference = nums[1] - nums[0] 扫描到下标 ``i`` 前,已经确认 ``nums[0..i-1]`` 的全部相邻差都等于 ``difference``。当前只需检查: .. code-block:: text nums[i] - nums[i-1] == difference 检查通过后,不变量扩展到 ``i``;任意一次失败都说明排序后的唯一候选不合法,可以立即返回 ``false``。 ``sortAndCheck`` 因而把阶乘级排列搜索降为一次排序和一次线性扫描。公开入口调用这一实现,因为代码短、状态少, 并且在题目规模下已经足够高效。按值接收副本也避免修改调用者传入的数组。 位置映射 ~~~~~~~~ 还可以继续消除排序。长度为 ``n`` 的等差数列一旦确定最小值 ``minimum`` 和最大值 ``maximum``,公差只能是: .. code-block:: text difference = (maximum - minimum) / (n - 1) 若跨度不能被 ``n - 1`` 整除,就不存在整数公差。公差确定后,任意元素 ``value`` 的目标下标也唯一确定: .. code-block:: text index = (value - minimum) / difference 因此 ``validatePositions`` 对每个元素检查三件事:偏移量能被公差整除、目标下标位于 ``[0,n-1]``、目标位置 尚未被其他元素占用。全部元素都通过时,恰好填满等差数列的全部位置。 重复与零公差 ~~~~~~~~~~~~ 当 ``maximum == minimum`` 时,所有元素相同,公差为 ``0``,结果直接为 ``true``。这一步必须在取模和除法前 处理,避免除以零。 当公差非零时,不同下标对应不同数值。若两个输入元素映射到同一个位置,说明出现了不允许的重复,同时必然有 另一个目标值缺失,立即返回 ``false``。 排序方法通过不一致的相邻差发现同一问题;位置映射则通过整除失败或位置冲突发现问题。两种方法验证的是同一个 等差结构。 三种方法的关系 ~~~~~~~~~~~~~~ 全排列方法不知道合法顺序,只能尝试所有候选。排序方法证明非递减顺序是唯一候选,删除了排列搜索。位置映射 进一步证明每个元素的目标位置都能直接计算,又删除了排序。 优化过程依次压缩的是: .. code-block:: text 全部排列 -> 唯一有序排列 -> 每个值的唯一目标位置 复杂度分析 ~~~~~~~~~~ ``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`` 计算,避免整数减法在更大数据范围下溢出。