Google on-site最后一面非常难的一道题目

线性算法（附带正确性证明）：
先考虑(A[0],A[1],A[2],A[3])，可以先调整A[0]和A[1]，保证A[0]<=A[1],然后调整A[2]和A[3]使得A[2]<=A[3]，如果A[1]<=A[2],swap(A[1],A[2]),注意这个时候无需再对A[0]和A[3]做任何变动，因为，实际上A[1]=max(A[1],A[2]),A[2]=min(A[1],A[2]),仍然可以满足A[0]<=A[1]<=max(A[1],A[2]), min(A[1],A[2])<=A[2]<=A[3],同时max(A[1],A[2])>=min(A[1],A[2])。再依次考虑(A[2],A[3],A[4],A[5]),(A[4],A[5],A[6],A[7])....
操作的次数不超过4＊N，即线性。
P.S:好奇的问一下，shuffle的时候不需要保证每一个可满足序列的随机性？

ototsuyume 发表于 2014-3-14 13:34
google电面的时候被问了这道题，这题也就看上去吼人而已，nlogn的算法是一下子能想出来的，线性的算法仔细 ...

make sense

void shuffle(int A[], int n)
          {
                  boolean isValley=false;
                  for(int i=1;i<n;i++){
                          if(isValley==true){//i-1 postion is valley
                                  if(A[i]<A[i-1]){
                                          A[i]+=A[i-1];A[i-1]=A[i]-A[i-1];A[i]=A[i]-A[i-1];//swap
                                  }
                                  isValley=false;
                          }
                          else{//i-1 postion is peak
                                  if(A[i]>A[i-1]){
                                          A[i]+=A[i-1];A[i-1]=A[i]-A[i-1];A[i]=A[i]-A[i-1];//swap
                                  }
                                  isValley=true;  
                          }
                  
                  }
          }
同学被面到，要求线性时间in place....贴下自己写的。如果要我当场写肯定写不出来。。。。

williamshyy 发表于 2015-3-20 09:50
void shuffle(int A[], int n)
          {
                  boolean isValley=false;

这题现在还在考？

timtam85 发表于 2015-3-20 12:33
这题现在还在考？

就前几天的事。。。

话说难度在什么地方？

1. public void shuffle(int[] arr) {
   
2.                 if(arr == null || arr.length < 2)        return;
   
3.                 for(int i = 1; i < arr.length; ++i) {
   
4.                         if(i % 2 == 0) {
   
5.                                 if(arr[i] > arr[i - 1]) {
   
6.                                         int tmp = arr[i - 1];
   
7.                                         arr[i - 1] = arr[i];
   
8.                                         arr[i] = tmp;
   
9.                                 }
   
10.                         } else {
    
11.                                 if(arr[i] < arr[i - 1]) {
    
12.                                         int tmp = arr[i - 1];
    
13.                                         arr[i - 1] = arr[i];
    
14.                                         arr[i] = tmp;
    
15.                                 }
    
16.                         }
    
17.                 }
    
18.         }

复制代码

1. public void suffle(int[] A){
   
2.                 for(int i = 0;i < A.length-1;i++){
   
3.                         if(i%2==0)
   
4.                                 if(A[i] > A[i+1]) swap(A, i, i+1);
   
5.                         else
   
6.                                 if(A[i] < A[i+1]) swap(A, i, i+1);
   
7.                 }
   
8.                 return;
   
9.         }
   
10. 
    
11.         private void swap(int A[], int a, int b){
    
12.                 int temp = A[a];
    
13.                 A[a] = A[b];
    
14.                 A[b] = temp;
    
15.         }

复制代码

Proof by induction:

(1) when there is only 1 number, it satisfies.

(2) when there are two numbers, at most one swap with fulfill.

(3) 1.suppose A[i-1] <= A[i],

      if A[i] >= A[i+1]

          satisfies

      else A[i] < A[i+1]

          since A[i-1] <= A[i], A[i] < A[i+1], A[i+1] is the peek of three

          swap A[i] and A[i+1]

      2. suppose A[i-1] >= A[i],

      if A[i] <= A[i+1]

          satisfies

      else A[i] > A[i+1]

          since A[i-1] >= A[i], A[i] > A[i+1], A[i+1] is the valley of three

          swap A[i] and A[i+1].

Proved.

感谢楼主面经，我最后一轮也是个这

我好久前就看到这道题。。。证明可能麻烦？
我一直想如果follow up问输出所有可能性，该怎么做。

求问一下
比如 [1, 2, 1, 1, 1, 1, 1, 1]这种情况的话
并没有办法shuffle出满意的结果
该如何证明呢