面试题 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
题解
按峰与谷的交替顺序:
- 峰-谷-峰-...
- 谷-峰-谷-...
选取一种顺序,谷-峰-谷-...,遍历元素,判断当前元素下标:
- 奇数:下标为1,3...,应该是峰,当前元素>=右边的元素,如果不满足,就交换当前元素和右边的元素。
- 偶数:应该是谷,当前元素<=右边的元素,如果不满足,交换。
查看代码
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int len=nums.size()-1;
//选取 谷-峰---顺序
for(int i=0;i<len;++i){
//奇数位:1,3...,应该是峰,当前元素>=右边的元素
if(i%2){
//不满足就交换
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]);
}
}
}
}
};