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

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

上一篇中介绍了一种算法,可以在复杂度为O(n)的情况下将一个数组中所有为0的元素移动到最末尾去,这一章使用一种更为精彩的算法实现这个效果

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

限制:只能遍历一次数组

代码实现如下

    private static void moveZero1(Integer[] arr){

        int k = 0;
        Integer tmp;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != 0){
                tmp = arr[i];
                arr[i] = arr[k];
                arr[k] = tmp;
                k++;
            }
        }
    }

就这么几行代码搞定?小编你是不是骗我!!

容我这一生中第一次撒谎:是的!这几行代码不可能实现

开始图解

一开始你的脑海里需要具备这个区域划分轮廓图

我们需要对整个数组划分为3个区域,全部都不是0,都是0未知区域

比如对于题目里的数组进行区域划分如下图

执行规律

  • 定义k,i游标。k位于黄色区域的最后一格,i位于蓝色区域最后一格。
  • 遍历数组,如果arr[i]≠0,则交换arr[k]与arr[i]的位置
  • 如果元素等于0,k不变,i继续向右移动

详细过程

结束

> 流程图结合代码很好理解~~~

# 算法  java  排序 

评论

Your browser is out-of-date!

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

×