yahoo面经

那就用index作为value，然后负数加个负号，bubble sort

1. public void re(int[] num){
   
2.         if(num==null || num.length<2) return;
   
3.         int i=0,j=1;
   
4.     while(j<num.length){
   
5.       if(num[i]>0) {i++;j++;}
   
6.       else{//num[i] is negative, search for the next positive index
   
7.         while(j<num.length&&num[j]<0) j++;
   
8.         if(j<num.length){
   
9.           int tmp=num[j];
   
10.           for(int t=j;t>i;t--) num[t]=num[t-1];
    
11.           num[i]=tmp;
    
12.           i++;
    
13.           j++;
    
14.         }
    
15.     }
    
16.   }
    
17. }

复制代码

raincoatrun 发表于 2016-11-18 07:23
那就用index作为value，然后负数加个负号，bubble sort

这样子似乎也不行。
1. 要求single iteration
2. Index作为Value，负数加上负号，那么会有一边是逆序的，如果AscendingOrder，那么负数部分逆序，如果是DescendingOrder，那么正数部分逆序。

这题是color sort 变型吧. LC 75.

Bubble sort idea

1. void part(vector<int>& vec) {
   
2.     for(int j = 0; j < vec.size(); j++) {
   
3.         if(vec[j] > 0) {
   
4.             for(int i = j; i-1 >= 0 && vec[i-1] < 0; i--)
   
5.                 swap(vec[i-1], vec[i]);
   
6.         }
   
7.     }
   
8. }
   

复制代码

bubble sort: O(n^2)
queue: O(n) scan data once

wangxinbo1123 发表于 2017-1-13 08:00
Bubble sort idea

这pass了多少遍？

这题要不就得多次，要不就得加额外存储空间，应该是加空间的意思吧。

补充内容 (2017-3-11 06:51):
这题 o(n) time, o(1)space不可能，理论上不可能。

zzpnm003 发表于 2017-3-11 06:32
这题要不就得多次，要不就得加额外存储空间，应该是加空间的意思吧。

补充内容 (2017-3-11 06:51):

为什么呢？我觉得two pointer然后像sort color那个方法一样就可以了啊

shiloh00 发表于 2017-3-14 03:26
为什么呢？我觉得two pointer然后像sort color那个方法一样就可以了啊

sort color 是array, 可以random access. 而且你要不就是比较排序nlog(n)，要不额外空间降时间。这里要求o(1)的空间。