1502. 判断能否形成等差数列

🟢   🔖  数组 排序  🔗 力扣 LeetCode

题目

A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Given an array of numbers arr, return true if the array can be rearranged to form anarithmetic progression. Otherwise, return false.

Example 1:

Input: arr = [3,5,1]

Output: true

Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]

Output: false

Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

题目大意

给你一个数字数组 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

解题思路

1. 等差数列的特性:

   • 对于一个等差数列，最大值和最小值确定后，每两个相邻数之间的差是固定的 (gap)。
   • 给定最小值 min 和间隔 gap，等差数列中每个数字 arr[i] 都应该满足： arr[i] = min + i * gap
   • 如果某个数不在其目标位置（即 arr[i] ≠ min + i * gap），可以将其与目标位置上的数交换，直到所有数都在目标位置。

2. 检查位置是否正确:

   • 如果当前数字已经在正确位置（即 arr[i] === min + i * gap），则继续处理下一个数字。
   • 如果当前数字不在正确位置：
     • 通过目标位置公式计算正确位置 pos = (arr[i] - min) / gap。
     • 检查 pos 是否有效（范围在 [0, n-1] 之间的整数），并确保目标位置的数字与当前数字不同，避免重复。

3. 交换数字:

   • 如果发现数字不在目标位置，交换 arr[i] 和 arr[pos]。
   • 重复检查新的 arr[i]，直到该位置数字满足等差数列的条件。

4. 继续遍历:

   • 处理下一个数字，直到所有数字都在正确位置。

复杂度分析

• 时间复杂度: O(n)，遍历数组两次：一次找最大值和最小值，一次调整元素位置。
• 空间复杂度: O(1)，原地修改数组，无额外空间。

代码

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canMakeArithmeticProgression = function (arr) {
	let min = Infinity,
		max = -Infinity;

	// 找到数组的最小值和最大值
	for (let num of arr) {
		if (num > max) max = num;
		if (num < min) min = num;
	}

	const n = arr.length;
	const gap = (max - min) / (n - 1);

	// 特殊情况，数组中的数全部相同时，也是等差数列，返回 true
	if (gap === 0) return true;

	let i = 0;
	while (i < n) {
		// 检查当前元素是否在正确位置
		if (arr[i] === min + i * gap) {
			i++;
		} else {
			const diff = arr[i] - min;

			// 检查当前元素是否满足等差公式
			if (diff % gap !== 0) return false;

			const pos = diff / gap;

			// 检查是否出现重复
			if (arr[pos] === arr[i]) return false;

			// 交换到正确位置
			let temp = arr[pos];
			arr[pos] = arr[i];
			arr[i] = temp;
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
1630	等差子数组		数组 哈希表 排序	🟠	🀄️ 🔗