这是小川的第 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 中, n 为 arr 的长度.
- 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 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/ba64b489f449