本文主要是介绍in-place算法之双指针法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
拿到这个题目,我首先的想法是比较暴力的算法。pre指针指向第一个不0的,再固定pre,扫描右边cur指向第一个为0的,然后交换位置。这样复杂度为O(n2)。
有一种比较简单的方法 -> in-place算法,无视0的存在。
直接找非0值,依次放到第0,1,2....位置。这样也需要设置两个指针分别维护应放位置以及非零值的位置。复杂度只有O(n)。
class Solution {public void moveZeroes(int[] nums) {//双指针法int n = nums.length;for(int i = 0, j = 0; i< n; i++){if(nums[i] != 0){int t = nums[i];nums[i] = nums[j];nums[j++] = t;}}}
}
这篇关于in-place算法之双指针法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!