查看: 8094|回复: 7
Leetcode Wiggle Sort II 求解！还没人给出过O(n)算法。。
精华主题学分
新农上路-加分请看每个版右边栏, 积分 93, 距离下一级还需 7 积分
在线时间 小时
注册一亩三分地论坛，查看更多干货！
才可以下载或查看，没有帐号？
大家好，求问一道题！这是leetcode上的Wiggle Sort II的原题：
Given an unsorted array nums, reorder it such that nums[0] & nums[1] & nums[2] & nums[3]....
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
这里不能像Wiggle Sort I 那样一次性遍历过数组只比较相邻的element。Discussion里面有人用先找中位数再swap的方法，复杂度是O(nlog(n))，而且过不了testcase [4, 5, 5, 6]。
现在OJ上貌似还没有O(n) time 和 O(1) space的方法。。。求大家一起提供思路啊！
精华主题学分
在线时间 小时
关注一亩三分地公众号：Warald_一亩三分地
先找中位数再swap,&&算法是O(n),& &找中位数， o(n) 就可以了
精华主题学分
在线时间 小时
关注一亩三分地微博：Warald
O(n)的思路和代码:
精华主题学分
在线时间 小时
本帖最后由 mumu007 于
03:04 编辑
class Solution {
public:
& & int quickSelect(vector&int&& nums, int left, int right, int n) {
& && &&&// http://www.hrwhisper.me/leetcode-wiggle-sort-ii/
& && &&&if(left &= right) return nums[right];
& && &&&int start = left, end = right + 1;
& && &&&int mid = nums[left];
& && &&&while(start & end) {
& && && && &while(++start & right && nums[start] & mid) ;
& && && && &while(--end & left && nums[end] & mid) ;
& && && && &if(start &= end)
& && && && &swap(nums[start], nums[end]);
& && &&&}
& && &&&swap(nums[left], nums[end]);
& && &&&if(n == end - left + 1) return nums[end];
& && &&&else if(n & end - left + 1) return quickSelect(nums, left, end - 1, n);
& && &&&else return quickSelect(nums, end + 1, right, n - (end - left + 1));
& & }
& & int transformInd(int i, int len) {
& && &&&if(i & (len && 1)) return i*2+1;
& && &&&else return (i - (len&&1))*2;
& & }
& & void wiggleSort(vector&int&& nums) {
& && &&&
& && &&&int len = nums.size();
& && &&&if(len & 2)
& && &&&int median = quickSelect(nums, 0, len - 1, (len + 1) && 1);
& && &&&int i = 0, j = 0, k = len - 1;
& && &&&while(i &= k) {
& && && && &int iT = transformInd(i, len), jT = transformInd(j, len), kT = transformInd(k, len);
& && && && &if(nums[iT] & median) {
& && && && && & swap(nums[iT], nums[jT]);
& && && && && & i++;
& && && && && & j++;
& && && && &}
& && && && &else if(nums[iT] & median) {
& && && && && & swap(nums[iT], nums[kT]);
& && && && && & k--;
& && && && &}
& && && && &else i++;
& && &&&}
& & }
};复制代码c++抛砖引玉，看过楼上的原帖写的，transformInd的作用就相当于
& & #define A(i) nums[(1+2*(i)) % (n|1)]// Index-rewiring.
精华主题学分
在线时间 小时
头像被屏蔽
提示: 作者被禁止或删除 内容自动屏蔽
精华主题学分
在线时间 小时
找中位数可以O(n)？ 题目要求不能用额外memory的。
找中位数 O(n) 算法导轮上有
精华主题学分
在线时间 小时
int transformInd(int i, int len) {
& && &&&if(i & (len && 1)) return i*2+1;
& && &&&else return (i - (len&&1))*2;
这个函数的意思是什么，不太明白，能不能解释一下
精华主题学分
在线时间 小时
int transformInd(int i, int len) {
& && &&&if(i & (len && 1)) return i*2+1;
& && &&&else return (i ...
Index的mapping。如果是偶数长度array[0,1,2,3,4,5] --& [1,3,5,0,2,4]如果是奇数长度array[0,1,2,3,4,5,6]--&[1,3,5,0,2,4,6]其实就是(2*i + 1) % (length | 1)这个表达式。
Mapping了以后即可以把它当成sort color那样做了
参考这个博客：
<form method="post" autocomplete="off" id="fastpostform" action="forum.php?mod=post&action=reply&fid=84&tid=161670&extra=&replysubmit=yes&infloat=yes&handlekey=fastpost"
onSubmit="
// TODO Howard 11/3/2015
var sbtn = $('fastpostsubmit');
sbtn.disabled =
sbtn.innerHTML = ' 回复发表中... ';
sbtn.setAttribute('background', sbtn.style.background);
sbtn.setAttribute('bordercolor', sbtn.style.borderColor);
sbtn.style.background = '#C7C7C7';
sbtn.style.borderColor = '#8B8B8B';
var form =
// --product--
var isValid = fastpostvalidate(form, null, 0);
if(!isValid) reoverBtn();
return isV
// --product--
// --testing--
//setTimeout(function() {
// var isValid = fastpostvalidate(form, null, 0);
// if(!isValid) reoverBtn();
//}, 2000);
// --testing--
您需要登录后才可以回帖
回帖并转播
回帖后跳转到最后一页
一亩三分地推荐 /5
地主Warald亲手做你的申请，针对你的背景和目标，考虑申请、学习、就业、移民等系列问题，制定申请策略。
“offer”指全额奖学金，免学费全免+每月工资，Berkeley, CMU, JHU, UIUC, Gatech, UMich, UCLA, Columbia，欢迎观赏。
电子工程、计算机、统计、金数金工、化工等, Stanford, Berkeley, CMU, Cornell, Yale, Columbia, Chicago, Duke, UPenn, UIUC, Brown, UMich, JHU等
有留学、申请、找工、职业规划上的难题？先上论坛提问！
论坛考古也帮不上忙，发帖得到的回答仍然不够？电话找Warald来解答！
WARALD新书上市啦：《你不知道的美国留学》清华大学出版社，各大电商发售
Powered by[leetcode]Sort&Colors
Given an array with n objects colored red, white or blue, sort
them so that objects of the same color are adjacent, with the
colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the
color red, white, and blue respectively.
You are not suppose to use the library's sort function for
this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm
using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's,
then overwrite array with total number of 0's, then 1's and
followed by 2's.
Could you come up with an one-pass algorithm using only
constant space?
class Solution {
& & void sortColors(int A[],
& // Start typing your C/C++ solution below
& // DO NOT write int main() function
& int tag[3] = {0,0,0};
& for(int i = 0;i &i++)
tag[A[i]]++;
& int count = 0;
& for(int i = 0;i & 3;i++)
& & & for(int j
= 0; j & tag[i] ;j++)
& & A[count++] =
//one-pass
class Solution {
& & void sortColors(int A[],
& // Start typing your C/C++ solution below
& // DO NOT write int main() function
& //one-pass algorithm
& int tag[3] = {};
& for(int i = 0; i & i++)
& & & int cur =
& & & for(int j
= 2;j &=j--)
& & A[tag[j]] =
& & tag[j]++;
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
class Solution {
ListNode *sortList(ListNode *head) ……
声明：该文章系网友上传分享，此内容仅代表网友个人经验或观点，不代表本网站立场和观点；若未进行原创声明，则表明该文章系转载自互联网；若该文章内容涉嫌侵权，请及时向
论文写作技巧
上一篇：下一篇：
相关经验教程}