首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >《双指针篇》---双指针算法原理

《双指针篇》---双指针算法原理

作者头像
用户11288958
发布2024-11-21 15:04:25
发布2024-11-21 15:04:25
4950
举报
文章被收录于专栏:学习学习

利用数组下标来充当指针。

1.双指针算法本质: 将数据划分为三个区间,我们以移动零为例: 给定数组中。 【0,left】:全是非0元素。 【left+1,cur-1】:全是0元素。 【cur,n-1】:待处理元素。

代码语言:javascript
复制
        public void moveZeroes(int[] nums) {
            //定义left和right双指针。并在right<n的情况下循环。
            //如果nums[right] != 0则交换left和right指向的元素。
            //若等于零则right++。
            //保证left之前的数据非零。left指向第一个零。
            //right之后的数据待处理。
            int left = 0,right = 0;
            int n = nums.length;
            while(right < n){
                if(nums[right] != 0){
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    left++;
                }
                right++;
            }
        }

2.拓展:快排(双指针算法是快排中最核心的一步)

快排里面最核心的一步就是数据划分这一步。 定义一个数组,我们设置一个基准元素tmp。将数组划分为两个部分。 左边全 <= tmp。 右边全 > tmp。 三个区间: 【0,left】:全是 ≤ tmp。 【left+1,cur-1】:全是 > tmp。 【cur,n-1】:待处理元素。 快排的双指针思想不适合处理很多数据都相同的情况。

后面有一道颜色划分的题目。 我们会把数组分成三块。用这个算法排序思想来解决快排是最好的解法。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-11-01,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 2.拓展:快排(双指针算法是快排中最核心的一步)
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档