【算法分析与设计】移动零

2024-01-09 15:55:07

题目

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

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

示例 1:

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

示例 2:

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

思路:

从前往后开始遍历,找到不为0就与前面的值进行交换,

直到交换到第一个回去不为0的值结束。

代码实现:

class Solution {
    public void moveZeroes(int[] nums) {
       int left=0;
       int right=nums.length-1;
       int temp=0;
        for(int i=0;i<nums.length;i++){
            for(int j=i;j>0;j--){
                if(nums[j-1]!=0){
                    break;
                }
                 temp=nums[j];
                 nums[j]=nums[j-1];
                 nums[j-1]=temp;
                
            
            }
        }
           
          
    }
}

击败5%的用户。。。

肯定不是这样写的,这样写时间复杂度应该到了nlogn了(emmm不会算)

想别的方法呃,。。。

ding ding ding dong 有了!!!

思路二:

可以利用双指针嘛。

left指针指向最初的位置

right从0开始遍历,找到不为0的数字就和left指针的值进行交换

之后left++;

最后right找到末尾后。直接将left右边的所有值置为0即可。

?开始都指向索引0的节点。

之后right++

?此时right指向索引为1的节点。这个节点的值为1就与left所指向的节点交换值之后,left++,right++

?发现right指向的为0,不处理下一个right++

发现right指向3 与left的节点值交换,left++.,right++?

之后right指向12 再交换,最后left的右边的所有节点置为0即可?

代码实现

class Solution {
    public void moveZeroes(int[] nums) {
       int left=0;

        for(int right=0;right<nums.length;right++){
            if(nums[right]!=0){
                nums[left]=nums[right];
                left++;
            }
        }
        for(int i=left;i<nums.length;i++){
            nums[i]=0;
        }
           
          
    }
}

nice! 通过成功

文章来源:https://blog.csdn.net/m0_62645012/article/details/135479063
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。