in-place算法之双指针法

本文主要是介绍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算法之双指针法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---