构造元素不等于两相邻元素平均值的数组

难度: Medium

给你一个 下标从 0 开始 的数组 nums ，数组由若干 互不相同的 整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都 不等于 其两侧相邻元素的 平均值 。

更公式化的说法是，重新排列的数组应当满足这一属性：对于范围 1 <= i < nums.length - 1 中的每个 i ，(nums[i-1] + nums[i+1]) / 2 不等于 nums[i] 均成立。

返回满足题意的任一重排结果。

示例 1：

输入：nums = [1,2,3,4,5]
输出：[1,2,4,5,3]
解释：
i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5

示例 2：

输入：nums = [6,2,0,9,7]
输出：[9,7,6,2,0]
解释：
i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3

提示：

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Submission

运行时间: 125 ms

内存: 28.9 MB

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i = 0 
        while i + 2 < n:
            if nums[i + 1] * 2 == nums[i] + nums[i + 2]:
                nums[i + 1], nums[i + 2] = nums[i + 2], nums[i + 1]
                i = i - 1 if i > 0 else i + 1
            else:
                i += 1
            
        return nums

Explain

该题解的核心思路是通过扫描数组并在发现任何位置i，其中元素nums[i+1]等于其相邻元素nums[i]和nums[i+2]的平均值时进行交换。具体地，如果nums[i+1] * 2等于nums[i] + nums[i+2]，则交换nums[i+1]和nums[i+2]的位置。为了确保所有可能的问题都被解决，如果发生了交换，算法会向后退一步重新检查，除非已经在数组的起始位置，这种情况下会向前移动一步继续检查。这样做的目的是为了处理可能由于交换引入的新的或未解决的条件。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)  # 获取数组长度
        i = 0  # 初始化索引i
        while i + 2 < n:  # 循环直到倒数第三个元素
            if nums[i + 1] * 2 == nums[i] + nums[i + 2]:  # 检查是否满足nums[i + 1]是nums[i]和nums[i + 2]的平均值
                nums[i + 1], nums[i + 2] = nums[i + 2], nums[i + 1]  # 如果是，则交换nums[i+1]和nums[i+2]
                i = i - 1 if i > 0 else i + 1  # 如果不在数组开头，则回退一步，否则向前移动一步
            else:
                i += 1  # 否则向前移动一步
        
        return nums  # 返回重排后的数组

Explore

当发现nums[i+1]等于nums[i]和nums[i+2]的平均值时，即nums[i+1] * 2 = nums[i] + nums[i+2]，此时交换nums[i+1]和nums[i+2]的位置后，新的nums[i+1]（原来的nums[i+2]）与nums[i]和原来的nums[i+1]（现在的nums[i+2]）的关系会改变。由于原来的nums[i+1]与nums[i+2]不同，交换后新的nums[i+1]不会再等于nums[i]和新的nums[i+2]的平均值，从而打破了原来的等式条件。

虽然算法在进行交换后会向后退一步重新检查，以防止引入新的问题，但由于每次交换都是为了解决特定的平均值等式问题，交换将改变邻接元素的关系，消除当前的不满足条件。这种策略通常不会导致无限循环，因为每次交换至少解决了一个具体的不满足条件，不过在某些特殊情况下还需要额外的逻辑来确保算法总是朝向终止条件前进。

在数组只有两个元素的情况下，由于算法的核心检查是基于三个连续元素的关系（即检查nums[i+1]是否等于nums[i]和nums[i+2]的平均值），因此这种情况下算法实际上不会进行任何操作。对于只有两个元素的数组，不存在第三个元素，因此不会有任何交换或检查发生，数组将保持原样。

题解中的方法依赖于交换来调整元素以避免任何元素等于其两侧元素的平均值。虽然这种方法在大多数情况下是有效的，但理论上存在某些特殊构造的数组，可能通过简单的交换无法满足所有条件，特别是在数组元素高度重复或排序特殊的情况下。在实际应用中，应考虑这种方法的局限性，并在必要时探索其他可能的解决方案。