fb 电面挂经

如果数学可以重复用的话，那最坏复杂度是 n^3吧？

say543 发表于 2017-4-8 13:38
lz move zero 那堤能说说怎做吗? 一直没找到answer...

two pointer

1. left = 0, right = arr.length -1
   
2. 
   
3. while (left < right) {
   
4.     while (left < right && arr[left] != 0) left++;
   
5.     while (left < right && arr[right] == 0) right --;
   
6. 
   
7.     if (left < right) {
   
8.        swap(arr, left, right);
   
9.        left++,  right --;
   
10.     }
    
11. }

复制代码

scredwood 发表于 2017-4-9 05:50
two pointer

move 最少的话，不要用这种办法。还有一种解法。要看题目要求，如果不用管后面的数字可以。
因为一个swap算移动两次，如果我们这样copy的话，每个0只要移动一次。

1. index = 0;
   
2. for (int i = 0; i < arr.length; i++) {
   
3.     if (arr[i] != 0) {
   
4.         arr[index++] = arr[i];
   
5.     }
   
6. }

复制代码

scredwood 发表于 2017-4-9 05:55
move 最少的话，不要用这种办法。还有一种解法。要看题目要求，如果不用管后面的数字可以。
因为一个swa ...

这个感觉算不上move最少。
即便是要考虑保持原来的顺序，你这里也最好加个判断 index!=i 再移动

sean1993519 发表于 2017-4-9 03:56
哈哈对对，脑抽了，光想着用map存index了，用array存确实好一点，请问一下最好的方法这么做是建个compara ...

是呀  应该是的

翻滚吧豆子 发表于 2017-4-9 07:22
这个感觉算不上move最少。
即便是要考虑保持原来的顺序，你这里也最好加个判断 index!=i 再移动

不然还能怎么少哇。

scredwood 发表于 2017-4-9 11:07
不然还能怎么少哇。

不保持原顺序的情况下，双指针是最少

求问如果要保留非0的顺序，是不是下面的方法比较好

1. public void moveZeroes(int[] nums) {
   
2.         int zeropos = 0;
   
3.         for (int curpos = 0; curpos < nums.length; curpos++) {
   
4.             if(nums[curpos] != 0 && zeropos != curpos){
   
5.                 nums[zeropos++] = nums[curpos];
   
6.             }else if (nums[curpos] != 0 && zeropos == curpos){
   
7.                 zeropos++;
   
8.             }
   
9.         }
   
10.         while(zeropos < nums.length){
    
11.             nums[zeropos++] = 0;
    
12.         }
    
13.     }

复制代码

sean1993519 发表于 2017-4-10 03:37
求问如果要保留非0的顺序，是不是下面的方法比较好

对，挺好了

谢谢分享！楼主好运！