21.LeetCode 283: MoveZeros

小灰灰 2022-02-14 08:11 144阅读 0赞

题目
    ：

/**
     * 283
     */
    public class MoveZeros {
    
        //时间复杂度:O(n)
        //空间复杂度：O(n)
        public void moveZeroes(int[] nums) {
    
            int[] temp = new int[nums.length];
            int j=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]!=0){
                    temp[j++]=nums[i];
                }
            }
            for(int i=0;i<j;i++){
                nums[i]=temp[i];
            }
            for(int i=j;i<nums.length;i++)
                nums[i]=0;
        }
    
        //时间复杂度O(n)
        //空间复杂度O(1)
        public void moveZeroes2(int[] nums) {
    
          int k=0;//nums[0,k)存放非0元素
            //遍历到i个元素后，保证[0,i]中所有的元素，都按顺序排列在[0,k)中
          for(int i=0;i<nums.length;i++){
              //遇到非0元素就移到nums[k]的位置，不在乎是否覆盖了0，
              // 最后遍历完了非0元素，补齐0
              if(nums[i]!=0)
                  nums[k++]=nums[i];//此时第i个元素按顺序放入了[0,k)中
          }
    
          //剩余的位置补0
          while(k<nums.length)
              nums[k++]=0;
        }
    
        //非0元素与0元素交换，交换的过程中0元素自动到后面
        public void moveZeroes3(int[] nums) {
    
            int k=0;//nums[0,k)存放非0元素
            //遍历到i个元素后，保证[0,i]中所有的非0 元素，都按顺序排列在[0,k)中
            //同时，[k,i]为0
            for(int i=0;i<nums.length;i++){
                if(nums[i]!=0) {
                    //数组全部是非0的
                    if(i!=k)
                        swap(nums,k++,i);//此时第i个元素按顺序放入了[0,k)中
                    else
                        //i==k
                        k++;
                }
            }
        }
    
        private void swap(int[] nums, int k, int i) {
            int tem = nums[k];
            nums[k]=nums[i];
            nums[i]=tem;
        }
    
        public static void main(String[] args) {
            int arr[] = {0,1,0,3,12};
            //new MoveZeros().moveZeroes(arr);
            new MoveZeros().moveZeroes3(arr);
            System.out.println(Arrays.toString(arr));
        }
    }