题目描述:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序
方法一:
思路:先遍历一次数组,计算数组中0的个数
再次遍历数组,把非零元素放到前面,然后把数组后面的元素用0填充
class Solution { public void moveZeroes(int[] nums) { int count = 0; for (int i=0;i< nums.length;i++){ if (nums[i]==0){ count++; } } for (int i=0,j=0;i分析:
时间复杂度:O(n)-----(达到3n)
空间复杂度:0(1)这是思路其实是知道了要移动的元素是0,实质上是覆盖0,而且最后还需要进行补0循环
方法二:
双指针遍历
左指针指向已处理好的序列的尾部,右指针指向待处理的序列的首部,右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移class Solution { public void moveZeroes(int[] nums) { int n = nums.length, left = 0, right = 0; while (right < n) { if (nums[right] != 0) { swap(nums, left, right); left++; } right++; } } public void swap(int[] nums, int left, int right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } }分析:
时间复杂度:O(n),比方法一的执行次数少
空间复杂度:O(1)欢迎分享,转载请注明来源:内存溢出
评论列表(0条)