2019-03-14-算法-进化（移动零）

末蓝、 2022-03-08 09:50 177阅读 0赞

**题目描述**  
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

**示例:**

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

**说明:**

1.  必须在原数组上操作，不能拷贝额外的数组
2.  尽量减少操作次数

/** * 思路1：从左向右遍历，遇到零就将零右边的未移位的(i, length-i)全部左移 * @param nums */
    	public void moveZeroes1(int[] nums) { 
    		int len = nums.length;
    		int count=0;
    		if(len ==0 || len==1) { 
    			return ;
    		}
            for(int i=0;i<len-count;i++) { 
            	if(nums[i] == 0) { 
            		int j=0;
            		count++;
            		for(j=i;j<len-count;j++) { 
            			nums[j]=nums[j+1];
            		}
            		nums[j]=0;
            		i--;
            	}
            }
        }
    	
    	/** * 思路1优化版：从左向右遍历，遇到零时判定后续零的数量，连续的零就统一移位。将零右边的未移位的(i, length-i)全部左移 * @param nums */
    	public void moveZeroes2(int[] nums) { 
    		int len = nums.length;
    		int count=0;
    		if(len ==0 || len==1) { 
    			return ;
    		}
    		int lianXu=0;
            for(int i=0;i<len-count+lianXu;i++) { 
            	if(nums[i] == 0) { 
            		lianXu++;
            		count++;
            	}else { 
            		if(lianXu !=0) { 
            			int j=0;
            			for(j=i-lianXu;j<len-count;j++) { 
            				nums[j]=nums[j+lianXu];
            			}
            			for(int k=0;k<lianXu;k++) { 
            				nums[j+k]=0;
            			}
            			i-=lianXu;
            			lianXu=0;
            		}
    			}
            }
        }

/** * 思路3：先遍历获取0的个数，然后遍历移动 * @param digits * @return */
    	public int[] moveZeroes3(int[] digits) { 
            int count=0,index=0;
    		for(int i=0;i<digits.length;i++) { 
    			if(digits[i] == 0) { 
    				count++;
    			}
    		}
    		if(count ==0||count==digits.length) { 
    			return digits;
    		}
    		
    		for(int i=0;i<digits.length;i++) { 
    			while(i<digits.length && digits[i] ==0) { 
    				i++;
    			}
    			if(index <digits.length-count) { 
    				digits[index++] =digits[i];
    			}
    		}
    		for(int i=digits.length-1;i>digits.length-1-count;i--) { 
    			digits[i]=0;
    		}
    		
    		return digits;
        }

/** * 思路4：遇到零，就去后边搜寻非零，能找到就互换位置，找不到就结束了 * @param digits * @return */
    	public int[] moveZeroes(int[] digits) { 
    		int nonZeroIndex=0, len=digits.length;
    		for(int i=0;i<len && nonZeroIndex<len;i++) { 
    			if(digits[i]==0) { 
    				for(int j=nonZeroIndex;j<len;j++) { 
    					if(digits[j] !=0) { 
    						digits[i]=digits[j];
    						digits[j]=0;
    						nonZeroIndex++;
    						break;
    					}
    				}
    			}else { 
    				nonZeroIndex++;
    			}
    		}
    		return  digits;
    	}

/** * 思路5：使用双指针法 * 指针1：数组下标 * 指针2：顺序变更后下一个非零数字下标 * @param digits * @return */
    	public int[] moveZeroes(int[] digits) { 
    		int nonZeroIndex=0;
    		for(int i=0;i<digits.length;i++) { 
    			if(digits[i]!=0) { 
    				digits[nonZeroIndex++]=digits[i];
    			}
    		}
    		while(nonZeroIndex<digits.length) { 
    			digits[nonZeroIndex++]=0;
    		}
    		return digits;
    	}

好的代码总是优美的，加油！