324 的 in place 和O(n)解法

我已经阵亡了。

我的解法是 nlgn ：

1. class Solution {
   
2. 
   
3.      public void wiggleSort(int[] nums) {
   
4. 
   
5.             Arrays.sort(nums);
   
6. 
   
7.             int n = nums.length;
   
8.          
   
9.             int mid = (n-1)/2;
   
10.             int k = 0;
    
11.             int[] temp = new int[n];
    
12. 
    
13.             for  (int i=0; i<=mid; i++) {
    
14. 
    
15.                                     temp[k] = nums[mid - i];        
    
16. 
    
17.                 if (k + 1 < n  )    temp[k + 1] = nums[n - 1 - i];  
    
18.    
    
19. 
    
20.                 k += 2;
    
21.             }
    
22.          
    
23.             System.arraycopy(temp, 0 ,nums, 0, n);
    
24.         }   
    
25. }

复制代码

题目的follow up是 in-place   而且 O(n)   --->  世界上真的有这个解法吗?  


欢迎分享!!!


补充内容 (2020-12-22 02:03):



谁能帮我找一下quick select的解法代码？  感谢万分！！！

就是 寻找K-th largest的 O(n)解法，只不过这里k = n/2。
算法原理也很简单，就是quick sort，只不过当你的pivot坐标等于K的时候，就中止迭代。因此pivot左边和右边都可能是未排序的，但一定满足左边的都小于等于pivot,右边都大于等于pivot.
这种算法平均来看就是O(n).如果完成所有迭代，则是O(nlogn)


完成quick partition，后面还有一个步骤是前后两部分穿插放置。这个要in-place还挺繁琐。

这个题目太难了吧。。。 楼主的解法已经又快又好了，我在leetcode run了一下faster than 90%

我用python试了一下in place，发现指针处理起来太复杂了。

p.s 我也不知道这个信息会打击还是安慰楼主，我leetcode看了一下，最近六个月只显示PayPal，而且频率很低，一年前Flag有考但是频率也都不高。楼主下次好运🍀

你把sorting改成 partition成前后两半 不就是O(n)了?
没学过算法的话请去看算法导论的quick sort部分

in place O(N)的话估计就是楼上说的做法，把sort变成只把数组分成<mid和>mid的部分，应该就是平均复杂度O(N)了，lz可以去leetcode和Wikipedia上找这个算法，关键字是quickselect

BFPRT quickselect 吗
看看程序员面试指南里面讲过

quick select 是重要考点，楼上们都提了，LZ 去好好补下课。所以世界上还真有。。。不过别怕哈，多举一反三就习惯这种follow up了

g00gley 发表于 2020-12-21 18:33
in place O(N)的话估计就是楼上说的做法，把sort变成只把数组分成mid的部分，应该就是平均复杂度O(N)了，lz ...

跪求这一题的解法感谢万分!!!!

raistlins 发表于 2020-12-22 02:29
就是 寻找K-th largest的 O(n)解法，只不过这里k = n/2。
算法原理也很简单，就是quick sort，只不过当你 ...

完成quick partition，后面还有一个步骤是前后两部分穿插放置