C/C++教程

LeetCode_算法入门_移动零

本文主要是介绍LeetCode_算法入门_移动零,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

(上述题目来源于LeetCode)

方法一(双指针):
class Solution {
    public void moveZeroes(int[] nums) {
        //数组长度
       int n = nums.length;
       //一次遍历
       //定义左右两个指针,左指针用来指向左边排好序的最后一个非零元素
       //右指针用来指向未排序的第一个元素
       int 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;
       }
}
方法二(两次遍历):
class Solution {
    public void moveZeroes(int[] nums) {
        //两次遍历
        //第一次遍历先将数组中所有不为0的数按序移到前面,第二次遍历只要把后面余下全部元素补0即可
        //定义一个指针指向当前排序元素
        int cur = 0;
        //第一次遍历,将不为0的元素移动到前面
        for(int i = 0; i < nums.length;i++){
            if(nums[i] != 0){
                nums[cur] = nums[i];
                cur++;
            }
        }
        //第二次遍历,将余下的元素补0
        for(int i = cur;i < nums.length;i++){
            nums[cur] = 0;
            cur++;
        }
    }
}
方法三(一次遍历,运用快排思想):
class Solution {
    public void moveZeroes(int[] nums) {
        //一次遍历,利用快速排序思想,将0作为中间分割元素
        //不等于0的放在前面,等于0的放在后面
        //定义指针指向前面不为0的最后一个元素
        int cur = 0;
        //一次遍历,把不为0的元素交换
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != 0){
                int temp = nums[cur];
                nums[cur] = nums[i];
                nums[i] = temp;
                cur++;
            }
        }
    }
}
这篇关于LeetCode_算法入门_移动零的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!