一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6237|回复: 7
收起左侧

[算法题] Leetcode Wiggle Sort II 求解!还没人给出过O(n)算法。。

[复制链接] |试试Instant~ |关注本帖
dengke 发表于 2016-1-2 09:40:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
大家好,求问一道题!这是leetcode上的Wiggle Sort II的原题:https://leetcode.com/problems/wiggle-sort-ii/
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(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的方法。。。求大家一起提供思路啊!






mkcing 发表于 2016-1-2 10:54:36 | 显示全部楼层
先找中位数再swap,  算法是O(n),   找中位数, o(n) 就可以了
回复 支持 反对

使用道具 举报

jefferyy 发表于 2016-1-6 07:03:02 | 显示全部楼层
回复 支持 反对

使用道具 举报

mumu007 发表于 2016-1-7 03:02:04 | 显示全部楼层
本帖最后由 mumu007 于 2016-1-7 03:04 编辑
  1. class Solution {
  2. public:
  3.     int quickSelect(vector<int>& nums, int left, int right, int n) {
  4.         // http://www.hrwhisper.me/leetcode-wiggle-sort-ii/
  5.         if(left >= right) return nums[right];
  6.         int start = left, end = right + 1;
  7.         int mid = nums[left];
  8.         while(start < end) {
  9.             while(++start < right && nums[start] < mid) ;
  10.             while(--end > left && nums[end] > mid) ;
  11.             if(start >= end) break;
  12.             swap(nums[start], nums[end]);
  13.         }
  14.         swap(nums[left], nums[end]);
  15.         if(n == end - left + 1) return nums[end];
  16.         else if(n < end - left + 1) return quickSelect(nums, left, end - 1, n);
  17.         else return quickSelect(nums, end + 1, right, n - (end - left + 1));
  18.     }

  19.     int transformInd(int i, int len) {
  20.         if(i < (len >> 1)) return i*2+1;
  21.         else return (i - (len>>1))*2;
  22.     }

  23.     void wiggleSort(vector<int>& nums) {
  24.         
  25.         int len = nums.size();
  26.         if(len < 2) return ;
  27.         int median = quickSelect(nums, 0, len - 1, (len + 1) >> 1);
  28.         int i = 0, j = 0, k = len - 1;
  29.         while(i <= k) {
  30.             int iT = transformInd(i, len), jT = transformInd(j, len), kT = transformInd(k, len);
  31.             if(nums[iT] > median) {
  32.                 swap(nums[iT], nums[jT]);
  33.                 i++;
  34.                 j++;
  35.             }
  36.             else if(nums[iT] < median) {
  37.                 swap(nums[iT], nums[kT]);
  38.                 k--;
  39.             }
  40.             else i++;
  41.         }
  42.     }
  43. };
复制代码
c++抛砖引玉,看过楼上的原帖写的,transformInd的作用就相当于
    #define A(i) nums[(1+2*(i)) % (n|1)]// Index-rewiring.
回复 支持 反对

使用道具 举报

eat0010 发表于 2016-2-25 01:28:03 | 显示全部楼层
mkcing 发表于 2016-1-2 10:54
先找中位数再swap,  算法是O(n),   找中位数, o(n) 就可以了

找中位数可以O(n)? 题目要求不能用额外memory的。
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-2-25 01:31:59 | 显示全部楼层
eat0010 发表于 2016-2-25 01:28
找中位数可以O(n)? 题目要求不能用额外memory的。

找中位数 O(n) 算法导轮上有
回复 支持 反对

使用道具 举报

Ran2446541820 发表于 2016-2-29 09:30:24 | 显示全部楼层
int transformInd(int i, int len) {
        if(i < (len >> 1)) return i*2+1;
        else return (i - (len>>1))*2;
    }
这个函数的意思是什么,不太明白,能不能解释一下
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-7-29 05:54:42 | 显示全部楼层
Ran2446541820 发表于 2016-2-28 17:30
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那样做了
参考这个博客:
http://bookshadow.com/weblog/2015/12/31/leetcode-wiggle-sort-ii/
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表