class Solution {
public:
vector<int> rearrangeArray(vector<int>& nums) {
}
};
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 <= 1050 <= nums[i] <= 105原站题解
php 解法, 执行用时: 596 ms, 内存消耗: 38.8 MB, 提交时间: 2023-09-07 15:32:41
class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
function rearrangeArray($nums) {
sort($nums);
$n = count($nums);
$i = 0;
$ans = array_fill(0, $n, 0);
foreach ( $nums as $num ) {
$ans[$i] = $num;
$i += 2;
if ( $i >= $n ) {
$i = 1;
}
}
return $ans;
}
}
java 解法, 执行用时: 55 ms, 内存消耗: 66.4 MB, 提交时间: 2023-09-07 15:30:02
class Solution {
public int[] rearrangeArray(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int [] res = new int [n];
int i = 0, l = 0, r = n - 1;
while (l <= r) {
res[i++] = nums[l++];
if (l <= r) res[i++] = nums[r--];
}
return res;
}
}
java 解法, 执行用时: 49 ms, 内存消耗: 60.8 MB, 提交时间: 2023-09-07 15:28:51
class Solution {
public int[] rearrangeArray(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int i = 0;
while (i+1 < n) {
int tmp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = tmp;
i += 2;
}
return nums;
}
}
cpp 解法, 执行用时: 212 ms, 内存消耗: 125.3 MB, 提交时间: 2023-09-07 15:27:28
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;
}
};
python3 解法, 执行用时: 268 ms, 内存消耗: 31.5 MB, 提交时间: 2023-09-07 15:26:43
'''
思路：排序后从中间分开，错开一位合并
'''
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
nums.sort()
i, n = 0, len(nums)
ans = [0 for _ in range(n)]
for v in nums:
ans[i] = v
i += 2
if i >= n:
i = 1
return ans
golang 解法, 执行用时: 268 ms, 内存消耗: 9.2 MB, 提交时间: 2023-09-07 15:23:53
func rearrangeArray(nums []int) []int {
sort.Ints(nums)
i, n := 0, len(nums)
ans := make([]int, n)
for _, v := range nums {
ans[i] = v
if i += 2; i >= n {
i = 1
}
}
return ans
}