数组划分/数组分块（双指针算法）

用户11162265

发布于 2024-11-20 14:26:04

2420

文章被收录于专栏：C语言C语言

题目链接：移动零

数组划分就是根据条件将数组划分成几类，将同类放在一起，该题就是将数组非0元素和0元素分开

原理：双指针算法（利用数组下标充当双指针）

两个指针作用：

cur：从左往右扫描数组，遍历数组

dest：已处理的区间内，非零元素的最后一个位置

cur左边表示处理过的，右边是待处理的；

[0,dest]这个区间是非0元素，[dest + 1, cur -1]这个区间是0元素,[cur , n - 1]是待处理的元素

如何做到：

cur从前往后遍历过程：

1、遇到0元素：cur++

2、遇到非0元素：

swap(dest + 1, cur);

dest++,cur++;

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;
        int dest = -1;
        while (cur != nums.length) {
            if (nums[cur] != 0) {
                dest++;
                int temp = nums[dest];
                nums[dest] = nums[cur];
                nums[cur] = temp;
            }
            cur++;
        }
    }
}

这个数组划分也是快速排序里最核心的一步。

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

原始发表：2024-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除

原理