lilntcode-508-摆动排序
2024-10-19 11:52:50
508-摆动排序
给你一个没有排序的数组,请将原数组就地重新排列满足如下性质
nums[0] <= nums[1] >= nums[2] <= nums[3]....注意事项
请就地排序数组,也就是不需要额外数组
样例
给出数组为 nums = [3, 5, 2, 1, 6, 4] 一种输出方案为 [1, 6, 2, 5, 3, 4]
标签
排序 快速排序 数组 谷歌
方法一(快排 + 交换,时间复杂度O(nlgn))
先将数组排序,然后交换第2位和第3位,第3位和第4位...
code
class Solution {
public:
/**
* @param nums a list of integer
* @return void
*/
void wiggleSort(vector<int>& nums) {
// Write your code here
int size = nums.size();
if (size <= 0) {
return;
}
sort(nums.begin(), nums.end());
for (int i = 1; i < size - 1; i += 2) {
swap(nums[i], nums[i + 1]);
}
}
};
方法二(找规律 + 交换,时间复杂度O(n))
- 当i为奇数时,nums[i] >= nums[i - 1]
- 当i为偶数时,nums[i] <= nums[i - 1]
- 那么只要对每个数字,根据其奇偶性,选择是否与上一个数交换即可
code
class Solution {
public:
/**
* @param nums a list of integer
* @return void
*/
void wiggleSort(vector<int>& nums) {
// Write your code here
int size = nums.size();
if (size <= 0) {
return;
}
for (int i = 1; i < size; i += 2) {
if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
swap(nums[i], nums[i - 1]);
}
}
}
};
最新文章
- JAVA 如何把request请求的参数,快速放到model对象中
- Sharepoint创建List
- [你必须知道的NOSQL系列]专题一:MongoDB快速入门
- CF 672C Recycling Bottles[最优次优 贪心]
- FreeBSD 9.1安装KMS 这是一个伪命题###### ,9....
- TYVJ1000 A+B problem [存个高精模板]
- struts 2.0部署
- 《REWORK》启示录 发出你的心声——程序员与身体
- java网络编程之UDP通讯
- apache开源项目--Camel
- 2014年10月16号--for语句实例
- 2015.9.11模拟赛 codevs 4159【hzwer的迷の数列】
- ios开发必备第三方库
- C#学习日志 day7 --------------LINQ与Lamda语句的初步尝试以及XML的生成
- lua脚本中字符串分割split
- AFNetworing进行POST上传 分类: ios技术 2015-04-01 17:03 73人阅读 评论(0) 收藏
- OC内存管理-OC笔记
- PAT甲级1068 Find More Coins【01背包】
- static全局变量与普通全局变量的区别,static局部变量与普通局部变量的区别,static函数与普通函数的区别
- android include使用[转]
热门文章
- Node.js http.createServer 简单服务配置
- 树莓派GPIO控制LED彩灯
- Linux了解一下
- C# 对DataTable的简单操作
- vue中-webkit-box-orient:vertical打包放到线上不显示
- 自己用原生JS写的轮播图,支持移动端触摸滑动,分页器圆点可以支持mouseover鼠标移入和click点击,高手看了勿喷哈
- 20155216 2016-2017-2 《Java程序设计》第七周学习总结
- 20155222 2016-2017-2 《Java程序设计》第4周学习总结
- Caliburn.Micro - Getting Started - Introduction
- spring_cloud多个微服务访问时偶发forward_error问题