leetcode hot 100 之【LeetCode 283. 移动零】 java实现

LeetCode 283. 移动零

题目描述

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

示例:

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

说明:

• 必须在单次遍历中修改数组，并在不接受任何额外空间的条件下完成。

Java 实现解法

方法一：双指针法

class Solution {public void moveZeroes(int[] nums) {int nonZeroIndex = 0; // 非零元素的索引for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {nums[nonZeroIndex++] = nums[i]; // 将非零元素移动到数组前面}}// 从非零元素的下一个索引开始，将数组填充为0while (nonZeroIndex < nums.length) {nums[nonZeroIndex++] = 0;}}
}

解题思路

• 双指针法：使用两个指针 nonZeroIndex 和 i。nonZeroIndex 用于记录数组中下一个非零元素应该放置的位置，而 i 用于遍历数组。
• 在遍历数组的过程中，如果当前元素 nums[i] 不为 0，则将其赋值给 nums[nonZeroIndex]，并将 nonZeroIndex 加 1。
• 如果当前元素为 0，则不进行操作，继续遍历。
• 当遍历完成后，nonZeroIndex 之后的数组位置都应该是 0，因此可以通过一个while循环将这些位置填充为 0。

这种方法的时间复杂度是 O(n)，其中 n 是数组 nums 的长度，因为我们只遍历了一次数组。空间复杂度是 O(1)，因为我们没有使用任何额外的空间，只是在原地修改了数组。

注：来源leetcode网站