一、题目描述:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums = [0] 输出: [0] 提示: 1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1 进阶:你能尽量减少完成的操作次数吗?
二、思路分析:
看到题目的一瞬间,我想到的时篡改就一个新的空数组,将非零的插入到新数组中,最后将0 补充在最后,但是题目中有要求时对原数组进行操作,刚好在20天算法刷题计划中该题属于双指针的题型范围,我按照双指针的思路进行思考,因为要保证非零元素的相对顺序,那么0元素与末尾非零元素交换的思路肯定是行不通了。
然后我想到将0 与相邻位非0元素进行交换,直到0全部移动到数组末尾的方式
首先初始化2个指针left = 0 ,right =0 ,循环至right到数组最后一位,当right指针指向元素不为0时,交互left和right元素,并将left和right向右移动一位,当right指向零时,将右指针移动一位,left不变,直到循环结束。
三、AC 代码:
class Solution { public void moveZeroes(int[] nums) { int n = nums.length, left = 0, right = 0; while (right < n) { if (nums[right] != 0) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; } right++; } } }
四、总结:
体验了3天,20天算法刷题计划中的题目对于这种新手感觉很有效果,题型归类好,多次刷同一类型的题目,题目选择比较简单,让