class Solution {
public:
void wiggleSort(vector<int>& nums) {
}
};
面试题 10.11. 峰与谷
在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。
示例:
输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3, 2, 3]
提示：
nums.length <= 10000原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-27 11:13:35
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
for i in range(n-1):
if i % 2 == 0:
if nums[i] < nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
else:
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
python3 解法, 执行用时: 52 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-27 11:13:23
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort()
n = len(nums)
for i in range(0, n, 2):
if i <= n - 2:
nums[i], nums[i+1] = nums[i+1], nums[i]
cpp 解法, 执行用时: 12 ms, 内存消耗: 13 MB, 提交时间: 2022-11-27 11:12:51
class Solution {
public:
void wiggleSort(vector<int>& nums) {
for(int i=1;i<nums.size();i++){
if(i%2==0){
if(nums[i]<nums[i-1]) swap(nums[i],nums[i-1]);
}
else{
if(nums[i]>nums[i-1]) swap(nums[i],nums[i-1]);
}
}
}
};
php 解法, 执行用时: 24 ms, 内存消耗: 19.9 MB, 提交时间: 2022-11-27 11:12:17
class Solution {
/**
* @param Integer[] $nums
* @return NULL
*/
function wiggleSort(&$nums) {
$len = count($nums);
for($i = 1; $i < $len; $i++){
if($i % 2 == 0){
if($nums[$i] > $nums[$i-1]){
$this->swap($nums,$i,$i-1);
}
}else{
if($nums[$i] < $nums[$i-1]){
$this->swap($nums,$i,$i-1);
}
}
}
}
function swap(&$nums, $i, $j){
$nums[$i] = $nums[$j] - $nums[$i];
$nums[$j] = $nums[$j] - $nums[$i];
$nums[$i] = $nums[$i] + $nums[$j];
}
}