Question

1968. Array With Elements Not Equal to Average of Neighbors

中文文档

Description

You are given a 0-indexed array nums of distinct integers. You want to rearrange the elements in the array such that every element in the rearranged array is not equal to the average of its neighbors.

More formally, the rearranged array should have the property such that for every i in the range 1 <= i < nums.length - 1, (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i].

Return _any rearrangement of _nums_ that meets the requirements_.

 

Example 1:

Input: nums = [1,2,3,4,5]
Output: [1,2,4,5,3]
Explanation:
When i=1, nums[i] = 2, and the average of its neighbors is (1+4) / 2 = 2.5.
When i=2, nums[i] = 4, and the average of its neighbors is (2+5) / 2 = 3.5.
When i=3, nums[i] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.

Example 2:

Input: nums = [6,2,0,9,7]
Output: [9,7,6,2,0]
Explanation:
When i=1, nums[i] = 7, and the average of its neighbors is (9+6) / 2 = 7.5.
When i=2, nums[i] = 6, and the average of its neighbors is (7+2) / 2 = 4.5.
When i=3, nums[i] = 2, and the average of its neighbors is (6+0) / 2 = 3.

 

Constraints:

• 3 <= nums.length <= 105
• 0 <= nums[i] <= 105

Solutions

Solution 1

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

class Solution {
  public int[] rearrangeArray(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int m = (n + 1) >> 1;
    int[] ans = new int[n];
    for (int i = 0, j = 0; i < n; i += 2, j++) {
      ans[i] = nums[j];
      if (j + m < n) {
        ans[i + 1] = nums[j + m];
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> rearrangeArray(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> ans;
    int n = nums.size();
    int m = (n + 1) >> 1;
    for (int i = 0; i < m; ++i) {
      ans.push_back(nums[i]);
      if (i + m < n) ans.push_back(nums[i + m]);
    }
    return ans;
  }
};

func rearrangeArray(nums []int) []int {
  sort.Ints(nums)
  n := len(nums)
  m := (n + 1) >> 1
  var ans []int
  for i := 0; i < m; i++ {
    ans = append(ans, nums[i])
    if i+m < n {
      ans = append(ans, nums[i+m])
    }
  }
  return ans
}

Solution 2

func rearrangeArray(nums []int) []int {
  rand.Seed(time.Now().UnixNano())
outer:
  for {
    rand.Shuffle(len(nums), func(i, j int) { nums[i], nums[j] = nums[j], nums[i] })
    for i := 1; i < len(nums)-1; i++ {
      if nums[i]*2 == nums[i-1]+nums[i+1] {
        continue outer
      }
    }
    return nums
  }
}