算法练习 · 将数组中的0全部移动到末尾(一)

算法练习 · 将数组中的0全部移动到末尾(一)

问题:如以下数组。将数组中的2个0移动到数组末尾

限制:只能遍历一次数组

步骤

  • 定义zerocnt变量存储0的个数

  • 如果arr[i] == 0,zerocnt加一,继续往后遍历

  • 如果arr[i] !=0,则进行位移操作,位移公式arr[i-zerocnt] = arr[i]

  • 最后将后面的数组全部替换为0即可

如下图所示

i = 0,zeroCnt=0。位置不变

i = 1,zeroCnt=0。位置不变

** i = 2,zeroCnt++ = 1。继续往右移动**

i=3,zeroCnt=1。代入公式可得arr[2] = arr[3]。如上图所示

i=4,zeroCnt++ = 2。继续往右移动

i=5,zeroCnt=2。代入公式可得arr[2] = arr[3]。如上图所示

i=6,zeroCnt=2。代入公式可得arr[4] = arr[6]

i=7,zeroCnt=2。代入公式可得arr[5] = arr[7]

将数组的最后zeroCnt个元素全部替换为0即可

java代码实现

    public static void testOptional(){

        Integer[] arrays = {2, 5, 0, 2, 0, 3, 8, 17};

        moveZero(arrays);

        for (Integer array : arrays) {
            System.out.print(array+"\t");
        }

    }

    private static void moveZero(Integer[] arr){

        //记录0出现的个数
        int zeroCnt = 0;

        for (int i = 0; i < arr.length; i++) {

            if(arr[i] != 0){
                arr[i - zeroCnt] = arr[i];
            }else{
                zeroCnt ++;
            }
        }

        //最后替换数组最末尾的zeroCnt个元素为0
        for (int j = zeroCnt; j>0; j -- ){
            arr[arr.length - j] = 0;
        }
    }

这种算法只需要遍历一次数组即可,O(n)时间复杂度,效率极快

# 算法  java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×