What is the key to solving 'Array With Elements Not Equal to Average of Neighbors'?

The key is using a greedy approach where you rearrange the array such that no element equals the average of its neighbors. Sorting and swapping adjacent elements often solves this problem.

Can the input array have duplicate elements?

No, the problem specifies that the array contains distinct integers. If duplicates were allowed, the solution would need additional handling.

What is the time complexity of solving this problem?

The time complexity is O(n log n) due to the sorting step, followed by a linear pass to rearrange the elements, making the overall complexity O(n log n).

Is it possible to solve the problem without sorting the array?

While sorting is a common approach, the problem can be solved without sorting by directly rearranging the elements based on their relationship with their neighbors, though this could be less efficient.

How does GhostInterview help with the greedy approach for this problem?

GhostInterview offers step-by-step guidance through the greedy approach, ensuring you understand the reasoning behind each step and how to rearrange the array efficiently.

#1968

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个下标从 0 开始的数组 nums ，数组由若干互不相同的整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都不等于其两侧相邻元素的平均值。更公式化的说法是，重新排列的数组应当满足这一属性：对于范围 1 中的每个 i ， (nums[i-1] + nums[…

数组贪心排序

题目描述

给你一个 下标从 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⁵

lightbulb

解题思路

方法一：排序

由于数组中的元素是互不相同的，我们可以先对数组进行排序，然后将数组分成两部分，将前一半的元素放到答案数组中的偶数位置，将后一半的元素放到答案数组中的奇数位置。这样，对于每个元素，它的两个相邻元素都不会等于它的平均值。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        m = (n + 1) // 2
        ans = []
        for i in range(m):
            ans.append(nums[i])
            if i + m < n:
                ans.append(nums[i + m])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should focus on the greedy nature of the solution, ensuring no element becomes the average of its neighbors.
question_mark
Look for an understanding of invariants and how the rearranged array maintains these properties after sorting.
question_mark
Evaluate the candidate's ability to handle edge cases where the smallest and largest values are at the boundaries of the array.

warning

常见陷阱

外企场景

error
Not considering the possibility of adjacent elements being too close, leading to violations of the average condition.
error
Failing to rearrange the array optimally, resulting in a non-working solution that does not break the neighbor average condition.
error
Overcomplicating the problem with unnecessary checks or operations that increase the time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Try the problem with arrays of varying lengths, from the minimum size to the maximum allowed by the constraints.
arrow_right_alt
Test with arrays where values are arranged in increasing or decreasing order, and analyze the effect on the solution's correctness.
arrow_right_alt
Introduce duplicate elements into the problem and adjust the constraints to see if the greedy approach can still be applied.

help

常见问题

外企场景

继续练习

#1996 游戏中弱角色的数量 #2007 从双倍数组中还原原数组 #1921 消灭怪物的最大数量