数据结构刷题 ——001

Han.miracle

发布于 2025-12-22 15:04:18

150

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

移动零：283. 移动零 - 力扣（LeetCode）

算法的思路：

利用双指针：

cur 往前进行寻找非0 的数

pre 负责标记该点没有处理过的下标

cur 找到了就进行交换

pre 进行交换完了，该点也处理完毕，我们就往后就行处理 0

【0，pre-1】是处理好的

【pre , cur 】都是0

【cur ,array.length-1】未处理的

这个方法跟我们前面学习的数据结构的快排的双指针差不多

import java.util.Arrays;

public class _001 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{2, 0, 1, 0, 4, 5, 23, 0, 1, 0};
        System.out.println("处理前：" + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("处理后：" + Arrays.toString(nums));
        // 预期输出：[2, 1, 4, 5, 23, 1, 0, 0, 0, 0]
    }

    static class Solution {
        public void moveZeroes(int[] nums) {

            if(nums.length <= 1){
                return;
            }
            int cur = 0;
            int prev = 0;
            for (cur = 0; cur < nums.length; cur++) {
                if(nums[cur] != 0){
                    swap(nums,prev,cur);
                    prev++;
                }

            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

第二种

算法的思路：

利用双指针：

cur 往前进行寻找非0 的数

pre 负责标记该点没有处理过的下标

cur 找到了就进行交换

pre 进行交换完了，该点也处理完毕，我们就往后就行处理 0

【0，pre】是处理好的

【pre+1 , cur -1 】都是0

【cur ,array.length-1】未处理的

先判断下标是否有效，再访问数组元素

package _001;

import java.util.Arrays;

public class _001_secord {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{2, 0, 1, 0, 4, 5, 23, 0, 1, 0};
        System.out.println("处理前：" + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("处理后：" + Arrays.toString(nums));
        // 预期输出：[2, 1, 4, 5, 23, 1, 0, 0, 0, 0]
    }

    static class Solution {
        public void moveZeroes(int[] nums) {

            if(nums.length <= 1){
                return;
            }
            int cur = 0;
            int prev = -1;
            for (cur = 0; cur < nums.length; cur++) {
               if(nums[cur] != 0){
                   prev++;
                   swap(nums,prev,cur);
               }

            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

1. 第一种划分：

【0，pre-1】：已处理好的非 0 元素区间（全部为非 0，且顺序保持原始）。
【pre，cur】：全为 0 的区间（这些 0 是待移到末尾的）。
【cur，array.length-1】：未处理的区间（包含未检查的非 0 和 0）。 逻辑适配：对应prev初始值为0的实现（如第一个代码）。
- 初始时pre=0，【0，pre-1】为空（还未处理元素）。
- 当cur找到非 0 元素时，交换pre和cur，此时pre位置变为非 0，加入【0，pre-1】区间，然后pre++（扩大已处理区间，同时【pre，cur】成为新的 0 区间）。

2. 第二种划分：

【0，pre】：已处理好的非 0 元素区间（全部为非 0）。
【pre+1，cur-1】：全为 0 的区间。
【cur，array.length-1】：未处理的区间。 逻辑适配：对应prev初始值为-1的实现（如第二个代码）。
- 初始时pre=-1，【0，pre】为空。
- 当cur找到非 0 元素时，先pre++（此时pre指向待填充位置），交换后【0，pre】成为新的已处理区间，【pre+1，cur-1】自然成为 0 区间。

核心一致性

两种划分的本质完全相同：

都是通过cur遍历寻找非 0 元素，通过pre标记 “下一个非 0 元素应该放置的位置”。
交换后，pre始终指向 “已处理区间的最后一个非 0 元素”（或其前一位），确保pre左侧全为非 0，pre和cur之间全为 0，未处理区间在cur右侧。

找到第一个0的位置，赋值给slow。
让fast从slow+1开始，找到第一个非0的位置。
交换slow和fast。
然后，slow++（此时，slow指向的是交换过来的非0元素的下一个位置，可能是0，也可能不是。如果原来是0，交换后变成了非0，那么slow++后，slow指向的是原来的fast位置，现在是0，所以下一次循环中，slow指向的是0，而fast会继续寻找非0元素。这样，就可以继续交换。

考虑另一个例子：[1,0,0,3,12] 初始：slow=0, fast=0 第一轮： fast=0，nums[fast]=1不为0，不进入第一个while。 slow=0，nums[slow]=1不为0，进入第二个while：slow++ => slow=1，nums[1]=0，退出。交换nums[0]和nums[1] => [0,1,0,3,12] 这里已经出问题了，我们把第一个非0元素变成了0，然后把它换到了后面。然后fast++ => fast=1, slow++ => slow=2

方法三：

package _001;

import java.util.Arrays;

public class _001_demo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0, 1, 0, 3, 12};
        System.out.println("原数组：" + Arrays.toString(nums));
        solution.moveZeroes(nums);
        System.out.println("处理后：" + Arrays.toString(nums));
    }
}

class Solution {
    public void swap(int fast, int slow, int[] nums) {
        int swap = nums[fast];
        nums[fast] = nums[slow];
        nums[slow] = swap;
    }

    public void moveZeroes(int[] nums) {
        // 边界保护：空数组/单元素数组直接返回
        if (nums == null || nums.length <= 1) {
            return;
        }
        int slow = 0;
        int fast = 0;
        while (fast <= nums.length - 1) {
            // 1. 修正：先判下标，再找非0元素（避免越界）
            while (fast <= nums.length - 1 && nums[fast] == 0) {
                fast++;
            }
            // 若 fast 遍历完数组，终止循环（避免无限循环）
            if (fast > nums.length - 1) {
                break;
            }
            // 2. 修正：先判下标，再找0元素（避免越界）
            while (slow < fast && slow <= nums.length - 1 && nums[slow] != 0) {
                slow++;
            }
            // 3. 交换：仅当 slow < fast 时执行
            if (slow < fast) {
                swap(fast, slow, nums);
            }
            // 4. 关键修正：指针递增移到分支外，确保必执行（避免无限循环）
            fast++;
            slow++;
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除

数组