这是小川的第392次更新,第423篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第255题(顺位题号是1089)。给定一个固定长度的整数数组arr,复制每次出现的零,将剩余的元素向右移动。

请注意,不会写入超出原始数组长度的元素。

对输入数组进行上述修改,不要从函数返回任何内容。

例如:

输入:[1,0,2,3,0,4,5,0]
输出:null
说明:调用函数后,输入数组被修改为:[1,0,0,2,3,0,0,4]

输入:[1,2,3]
输出:null
说明:调用函数后,输入数组被修改为:[1,2,3]

注意

  • 1 <= arr.length <= 10000

  • 0 <= arr [i] <= 9

02 第一种解法

新建一个List,遍历arr中的元素,如果为0,添加两次到List中,然后将List中的前n个元素回写到arr中,narr的长度。

public void duplicateZeros(int[] arr) {
    List<Integer> list = new ArrayList<Integer>();
    for (int num : arr) {
        if (num == 0) {
            list.add(0);
        }
        list.add(num);
    }
    for (int i=0; i<arr.length; i++) {
        arr[i] = list.get(i);
    }
}


03 第二种解法

我们也可以不使用List,将arr复制一份出来,创建一个索引,遍历复制数组,将元素回写到arr中,遇到0就重复赋值一次。

public void duplicateZeros2(int[] arr) {
    int n = arr.length, index = 0;
    int[] copy = arr.clone();
    for (int num : copy) {
        if (index >= n) {
            break;
        }
        if (index+1 < n && num == 0) {
            arr[index++] = 0;
            arr[index++] = 0;
        } else {
            arr[index++] = num;
        }
    }
}


04 第三种解法

我们也可以不使用额外的空间,通过双指针来实现。

先遍历arr,统计其中元素值为0的元素个数,记为count,从后往前遍历,一个长度为arr的长度,另外一个长度为arr的长度加count,遇到0就重复回写一次。

public void duplicateZeros3(int[] arr) {
    int count = 0;
    for (int num : arr) {
        if (num == 0) {
            count++;
        }
    }
    int n = arr.length, n2 = n + count;
    // i是原数组的索引,j是原数组的长度加count
    for (int i=n-1, j= n2-1; i < j; i--, j--) {
        if (arr[i] != 0) {
            if (j < n) {
                arr[j] = arr[i];
            }
        } else {
            // 遇到0,再重复一次
            if (j < n) {
                arr[j] = arr[i];
            }
            j--;
            if (j < n) {
                arr[j] = arr[i];
            }
        }
    }
}


05 小结

算法专题目前已连续日更超过八个月,算法题文章261+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!