[LeetCode] 283. Move Zeroes

最新推荐文章于 2024-09-01 11:29:54 发布

Ber03

最新推荐文章于 2024-09-01 11:29:54 发布

阅读量162

点赞数

分类专栏： LeetCode 双指针法文章标签： LeetCode 双指针法

本文链接：https://blog.csdn.net/Bertram03/article/details/97172939

版权

LeetCode 同时被 2 个专栏收录

165 篇文章

订阅专栏

双指针法

19 篇文章

订阅专栏

原题链接：https://leetcode.com/problems/move-zeroes/

1. 题目介绍

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
给出一个数组nums，写一个函数，将数组所有的零都移动到最后面去，同时需要保持其他非零元素的相对顺序不变。

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:
注意：
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
你必须在原有的数组上进行操作，不能复制原有的数组。
将操作的次数尽量减少。

2. 解题思路

双指针法

本题可以使用双指针法解决。
设定左指针 left，left 一开始指向数组的第0个元素。
设定右指针 i ，i 一开始也指向数组的第0个元素。
然后 i 逐步向右移动，如果遇到非零的元素，nums[i] 就和 nums[left] 进行交换。交换后，left向右移动1步。

最坏的情况是，整个数组中没有0，那么left 和 i 一直都会指向同一个元素，这个元素自己和自己交换。
最好的情况是，如果数组中全部都是0，那么left 始终指向第一个元素，i 则是一路向右移动，一次都不需要交换。

时间复杂度：O(n)
空间复杂度：O(1)
实现代码

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