F家onsite面经，被要求加面

siren01 发表于 2015-3-31 18:09
我也是加面，你现在结果怎么样了

我14号才面。。。

brainrpi 发表于 2014-12-16 00:11
不好意思哈，我有点不太懂这个follow up和原题的区别。是用两个指针一左一右往内缩进吗？遇到改换的换？
...

我觉得是这样：
两种方法：
1。 每一个数组值都读写到了

1. def moveZeros1(arr):
   
2.         if not arr:
   
3.                 return
   
4.         index = 0
   
5.         for i in range(len(arr)):
   
6.                 if arr[i] != 0:
   
7.                         arr[index] = arr[i]
   
8.                         index += 1
   
9. 
   
10.         while index < len(arr):
    
11.                 arr[index] = 0
    
12.                 index += 1

复制代码

2。 用quicksort 的 partition 的话只需要做交换，所以可以减少读写次数
这里的0相当于就把它甩到数组末尾就可以了

1. def moveZeros(arr):
   
2.         if not arr:
   
3.                 return
   
4.         lastIndex = len(arr) - 1
   
5.        
   
6.         i = 0
   
7.         while i < lastIndex:
   
8.                 if arr[i] == 0:
   
9.                         arr[i], arr[lastIndex] = arr[lastIndex], arr[i]
   
10.                         lastIndex -= 1
    
11.                 else:
    
12.                         i += 1

复制代码

第一题的follow up应该是这个意思：

这题有两种做法，需要操作的次数是不一样的。

一种是两个指针，都从左边开始，往右走。第一个指针碰到零了就停下，然后第二个指针往后走，找到第一个非零，两个swap，如此循环，直到结束。这样有点儿像冒泡，需要不断的移动零。比如［0 1 2 3］，第一次移动后是：
［1 0 2 3］，然后
［1 2 0 3］，然后
［1 2 3 0］，总共得swap 3 次

第二种就是一左一右两个指针往中间走，碰到非法的就swap，这样需要的操作次数＝存在几个零。比如上面的［0 1 2 3］，一次swap就OK了：［3 1 2 0］

估计楼主一开始的方法是第一种，所有有了follow up，让写第二种。

其实仔细想一下，第一种就是冒泡排序用到的方式啊，一个一个swap，而第二种方法对应快排。当然第一种方法也有好处，它可以保证非零元素最后不打乱顺序。