move zero follow-up

问个问题 move zero leetcode 那题， how to minimize the number of overwrite ？ 能提供下思路吗？ 也是fb长考的 感谢

如果0少的话就换0，如果0多的话就换非零。连ambari的人都想得到，你还去啥facebook，要啥自行车。。。

1. public static void moveZeroes(int[] nums){
   
2.                 int zeroNum = 0;
   
3.                 for(int i = 0; i < nums.length; i++){
   
4.                         if(nums[i] == 0){
   
5.                                 zeroNum++;
   
6.                         }else{
   
7.                                 if(zeroNum != 0){
   
8.                                         nums[i - zeroNum] = nums[i];
   
9.                                 }
   
10.                         }
    
11.                 }
    
12.                 for(int i = nums.length - zeroNum; i < nums.length; i++){
    
13.                         if(nums[i] != 0){
    
14.                                 nums[i] = 0;
    
15.                         }
    
16.                 }
    
17.         }

复制代码

我写的代码，欢迎发表意见，应该是write次数最少的了

我一辈子赖美帝 发表于 2017-11-13 06:39
yes,我已经用大数据数组测试了5种实现，
你的solution的operation次数最少。

这个才是最优解

public static void moveZeroes(int[] nums) {
                  int right = nums.length-1;
                  int operations=0;
          for(int left = 0; left < nums.length; left++){
                  if(left>right){
                      nums[left]=0;
                      operations++;
                      continue;
                  }                 
                  if(nums[left] != 0){
                          continue;
                  }
                  while (nums[right] == 0) right--;
                  nums[left]=nums[right];
                  operations++;
                  right--;
          }
          System.out.println(operations);
        }

我想的是计算每个非0元素num[i]之前0的个数，如果0的个数是1，num[i]往前挪一个位置就是了，如果是2，往前挪两个，以此类推。最后一个数挪完了就往剩下的位置里填0。因为是从前往后遍历，所以这样move不会覆盖数组里的非零元素。
我认为这是move最少的了吧，因为每个元素都直接挪到目的位置....

smellycat 发表于 2016-9-30 07:35
我想的是计算每个非0元素num之前0的个数，如果0的个数是1，num往前挪一个位置就是了，如果是2，往前挪两个 ...

你这样的话complexity好高啊 每次数0的个数 1 + 2 + 3 + 4 + n - 1 = O(n^{2})

kobe24 发表于 2016-9-30 08:11
你这样的话complexity好高啊 每次数0的个数 1 + 2 + 3 + 4 + n - 1 = O(n^{2})

不用啊，扫一遍数组就是啦，count表示当前数到的0的个数，count的是递增的，每碰到一个非0数num[i],就把它移到i-count的位置。complexity是O（n）。

two point + swap?

smellycat 发表于 2016-9-30 07:35
我想的是计算每个非0元素num之前0的个数，如果0的个数是1，num往前挪一个位置就是了，如果是2，往前挪两个 ...

如果是11101001，最后一个1前面有3个0，往前移三位，不是就把倒数第二个1覆盖了。。。

wza13579 发表于 2016-9-30 09:35
如果是11101001，最后一个1前面有3个0，往前移三位，不是就把倒数第二个1覆盖了。。。

因为是从左往右scan看每个数是不是可以移，倒数第二个1因为它的前面有一个1，所以往前移了一位，所以最后一个1往前移不会覆盖到倒数第二个1

smellycat 发表于 2016-9-30 11:55
因为是从左往右scan看每个数是不是可以移，倒数第二个1因为它的前面有一个1，所以往前移了一位，所以最后 ...

thx。好思路。但感觉这个移动步数跟双指针没区别。但如果不考虑移动后剩下的元素（比如10203 －》 123**），确实是最好的办法了。不知道是否理解正确。