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

给你一个 下标从 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 <= 105
• 0 <= nums[i] <= 105

方法一：排序

思路与算法

假设 nums 的长度为 n，由于 nums 中不含有数值相同的元素，因此我们一定可以将 nums 分成长度为 m = \lfloor (n + 1) / 2 \rfloor 与长度为 n - m 的两部分，其中第一部分的任何一个元素一定小于第二部分的任意一个元素。这也意味着，第一部分任意两个元素的平均值一定不会等于第二部分的任意一个元素，反之亦然。

那么，我们可以将数值较小的第一部分的元素放入重排数组的偶数下标（包含 0），并将数值较大的第二部分的元素放入重排数组的奇数下标，这样重排后的数组一定满足题目的要求。

本文中，我们将 nums 升序排序，然后依次将第一部分和第二部分的元素放入重排数组中，最终返回重排后的数组作为答案。

代码

[sol1-C++]

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        // 将数组排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int m = (n + 1) / 2;
        vector<int> res;
        for (int i = 0; i < m; ++i){
            // 放入数值较小的第一部分元素
            res.push_back(nums[i]);
            if (i + m < n){
                // （如果有）放入数值较大的第二部分元素
                res.push_back(nums[i + m]);
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        # 将数组排序
        nums.sort()
        n = len(nums)
        m = (n + 1) // 2
        res = []
        for i in range(m):
            # 放入数值较小的第一部分元素
            res.append(nums[i])
            if i + m < n:
                # （如果有）放入数值较大的第二部分元素
                res.append(nums[i + m])
        return res

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 nums 的长度。即为排序数组的时间复杂度。

• 空间复杂度：O(1)，输出数组不计入空间复杂度。