`
mabusyao
  • 浏览: 253296 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

数组双指针算法的研究

 
阅读更多
双指针算法在数组/链表操作中应用广泛,很多时候,为了完成某个目的,常常需要不断的循环检查数组或是链表,又或者需要拷贝出额外的存贮空间来保存中间结果。在其中的一些情况下,如果能够合理的应用数组双指针,则可以极大的减少算法的时间复杂度和空间复杂度。
 
根据初始双指针的位置,可以将之分为双头部指针,双尾部指针以及头尾指针.
 
今天我们就来看几个利用数组双指针算法的例子。
 

案例1: 给定一个数组,求出索引i和j,使得i和j之间的子串为符合某个特定条件的子串。

 
这种类型有很多,主要是为了找出符合特定条件的子串,下面是几个特定条件的例子:
1. Sum(i -> j) > k 的最短子数组, k为某常量
2. Sum(i -> j) < k 的最长子数组, k为某常量
3. Sum(i -> j) = k 且 j - i = ,m 的最子数组, k为某常量
4.(j - i)* min(array[i], array[j]) 最大的子数组
 
以第一道题为例,就是为了找出和大于某个特定常量的最短子数组。
 
常见的解决方案可以通过找出所有符合条件的子数组,然后根据这些子数组的长度,选出最短的那个。算法的时间复杂度为O(nlogn),空间复杂度为O(n^2)
 
当然我们也可以利用双头部指针算法,
 
     - 初始索引i和j指向数组头部,计数器maxLength为0.
     - 迭代: 
          - 如果i与j之间的子数组的和大于k,则判断j -i + 1是否小于maxLength,若是,则将maxLength更新为j -i + 1,i++并移向下一组candidate。
          - 如果i与j之间的子数组的和小于等于k,则j++。
          - 当j到达数组尾部时,结束迭代。
     - 在迭代过程中,计算i与j之间子数组的和并不需要每次都重新计算,而是只要相应增量的加上j位置的值或是减去i位置的值即可。
 
我们将时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码:
 
public class MinSubArrayLen {
    public static void main(String[] args) {
        MinSubArrayLen ms = new MinSubArrayLen();
        System.out.println(ms.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
    }

    /**
     * 双指针-双头部算法
     *
     * @param s
     * @param nums
     * @return
     */
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;

        int i = 0;
        int j = 0;
        int min = Integer.MAX_VALUE;

        int sum = nums[0];
        while(true) {
            if (sum < s) {
                j++;
                if (j == nums.length) break;

                sum += nums[j];
            } else {
                min = Math.min(min, j - i + 1);
                sum -= nums[i];
                i++;
            }
        }

        return min == Integer.MAX_VALUE ? 0 : min;
    }
 
 
许多类似的题目(找出符合特定条件的子串)都可以利用这样的算法来解决,区别仅仅是在于初始状态指针的位置。
 
第四道题目的原题是这样的: 
     给定 n个非负整数a1,a2,... an, 每个ai代表位置为i,高度为ai的柱子,那么求i和j使得ai到aj所能形成的正方形最大(即(j - i)* min(ai,aj))
 
这个问题也还是可以通过双指针算法来解决,区别在于指针的初始状态为一头一尾
     - 初始索引i和指向数组头部,j指向数组尾部,计数器maxArea为0.
     - 迭代: 
          - 计算当前Area,若大于maxArea则替换。
          - 若a[i] < a[j], 则i++, 否则j--。
          - 当i与j相遇时,迭代结束。
 
时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码:
 
public class Solution {
    public int maxArea(int[] height) {
        int len = height.length, low = 0, high = len -1 ;
        int maxArea = 0;
        while (low < high) {
            maxArea = Math.max(maxArea, (high - low) * Math.min(height[low], height[high]));

            if (height[low] < height[high]) {
                int lowbaseline = height[low];
                while(true) {
                    if (low >= high || height[low] > lowbaseline) break;
                    low++;
                }
            } else {
                int highbaseline = height[high];
                while(true) {
                    if (high <= low || height[high] > highbaseline) break;
                    high--;
                }

            }
        }

        return maxArea;
    }
}
 
 
 
还有一类问题,它们并没有找出某个特定子串的要求,但是为了达到常量级的空间复杂度,通常也可以使用双指针算法:
5. 将数组拆分为左奇右偶
6. 检查链表是否有环
7. 快速排序
 

 

第五个例子要求找出数组中所有的奇数和偶数,并将奇数放在数组的前端,偶数放在数组的后端。
 
这个题目其实很简单,但是要想达到常量级的空间复杂度,则要求必须是一个on place的算法,我们也可以利用双指针来做到这一点。
 
基本的思路其实是和快速排序的partition一致,关于快排的讨论已经很多了,这里不再赘述。 我们看一下快排的partition代码。为了解释算法本身,并没有做任何优化:
 
public class QuickSort {

    /**
     * 取数组的最后一位做为中位数。
     * 从开始进行遍历,如果某值小于该中位数,i向前一步走,i与j的数值互换。
     * 如果某值大于该中位数,则j++。
     * 算法很精巧,始终维持i与j之间正好是所有大于中位数的值。
     *
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int partition(int[] array, int start, int end) {
        int mediumVal = array[end];
        int i = start - 1;

        for (int j = start; j < end; j++) {
            if (array[j] <= mediumVal) {
                i++;
                exchange(array, i, j);
            }
        }

        exchange(array, i + 1, end);

        return i + 1;
    }
}
 
 
第六个例子实在是经典算法考题,判断一个链表中是否有环,只要用两个指针,一个每次走一步,另一个每次走两步,看足够多的步之后,两个指针是否会相遇即可。同样也不需要额外的存储空间。
 
这里就总结了关于双指针算法的7种常见使用场景,欢迎大家提供更多的好例子。
分享到:
评论

相关推荐

    python入门-30.寻找列表中只出现一次的数字-寻找单身狗.py

    python入门-30.寻找列表中只出现一次的数字——寻找单身狗.py

    布尔教育linux优化笔记

    linux优化笔记,配套视频:https://www.bilibili.com/list/474327672?sid=4496133&spm_id_from=333.999.0.0&desc=1

    知识付费系统-直播+讲师入驻+课程售卖+商城系统-v2.1.9版本搭建以及资源分享下载

    知识付费系统-直播+讲师入驻+课程售卖+商城系统-v2.1.9版本搭建以及资源分享下载,CRMEB知识付费分销与直播营销系统是由西安众邦科技自主开发的一款在线教育平台,该系统不仅拥有独立的知识产权,还采用了先进的ThinkPhp5.0框架和Vue前端技术栈,集成了在线直播教学及课程分销等多种功能,旨在为用户提供全方位的学习体验,默认解压密码youyacaocom

    美妆神域-JAVA-基于springBoot美妆神域设计与实现

    美妆神域-JAVA-基于springBoot美妆神域设计与实现

    原生js制作Google粘土logo动画涂鸦代码.zip

    原生js制作Google粘土logo动画涂鸦代码.zip

    golin 扫描工具使用, 检查系统漏洞、web程序漏洞

    golin 扫描工具使用, 检查系统漏洞、web程序漏洞

    原生态纯js图片网格鼠标悬停放大显示特效代码下载.zip

    原生态纯js图片网格鼠标悬停放大显示特效代码下载.zip

    用AWLUM进行灰色编码2^2n-QAM调制的精确率Matlab代码.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    去水印web端独立版web

    去水印web端独立版web

    原生js制作左侧浮动可折叠在线客服代码.zip

    原生js制作左侧浮动可折叠在线客服代码.zip

    Chrome 谷歌浏览器下载

    Chrome 谷歌浏览器下载

    亲测全新完整版H5商城系统源码 附教程

    全新完整版H5商城系统源码 自己花钱买的,亲测可用,需要自行下载 H5商城系统设置是实现商城基本功能的核心部分,涵盖了从网站配置、短信和支付配置,到商品、工单、订单、分站和提现管理等多个模块的设置。以下是详细的设置指南,帮助您快速上手并高效管理商城系统。 测试环境:Nginx+PHP7.0+MySQL5.6 1. 网站配置 设置商城名称、LOGO、标题、联系方式和SEO关键词等,确保商城专业和易于搜索。 2. 短信配置 配置短信接口和模板,用于发送订单通知、验证码等,提升用户体验。 3. 支付接口配置 配置微信、支付宝等支付接口,填写API密钥和回调地址,确保支付流畅。 4. 商品分类管理 对商品进行分类和排序,设置分类名称和图标,便于用户查找商品。 5. 商品管理 添加和管理商品信息、规格、图片等,确保商品信息准确丰富。 6. 工单管理 查看和回复用户工单,记录售后问题,提升用户服务质量。 7. 订单管理 查看订单详情,更新订单状态,支持批量导出,方便订单跟踪。 8. 分站管理 创建不同区域分站,设置权限,统一管理各区域市场。 9. 提现管理

    短信3.141592672893982398674234

    apk安装包

    原生js选项卡插件自定义图片滑动选项卡切换.zip

    原生js选项卡插件自定义图片滑动选项卡切换.zip

    1-宗教信息佛教佛寺寺庙庵堂相关数据-社科数据.zip

    宗教信息佛教佛寺寺庙庵堂相关数据集提供了全国各个地区省市县各个佛教寺庙的详细信息。这些数据不仅包括寺庙的名称和负责人姓名,还涵盖了所属省份、地级市、区县、具体地址、建立日期以及支派类别等关键信息。该数据集整理了超过3万条样本,为研究中国佛教寺庙的分布、历史和文化提供了丰富的第一手资料。这些信息有助于了解佛教在中国的传播和发展,以及寺庙在社会和文化中的作用。数据的整理和提供,对于宗教学、社会学、历史学和文化研究等领域的学者来说,是一个宝贵的资源。

    线性电阻网络的等效电阻计算Matlab代码.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    简单的 Python 版本管理.zip

    简单的 Python 版本管理pyenvpyenv 可让您轻松在多个 Python 版本之间切换。它简单、不引人注目,并遵循 UNIX 传统,即使用单一用途的工具来做好一件事。该项目由rbenv和 ruby​​-build分叉而来,并针对 Python 进行了修改。pyenv 的作用是什么......允许您根据每个用户更改全局 Python 版本。为每个项目的 Python 版本提供支持。允许您使用环境变量覆盖 Python 版本。一次搜索多个 Python 版本的命令。这可能有助于使用tox跨 Python 版本进行测试。与 pythonbrew 和 pythonz 相比,pyenv没有……依赖于Python本身。pyenv由纯shell脚本制作。不存在Python的引导问题。需要加载到你的 shell 中。相反,pyenv 的 shim 方法通过向你的 中添加目录来工作PATH。管理虚拟环境。当然,你可以自己创建虚拟环境 ,或者使用pyenv-virtualenv 来自动化该过程。目录安装获取 PyenvLinux/UNIX自动安装程序基本

    Notepad-v2.20工具,是替代Notepad++的首选工具

    Notepad-v2.20工具,是替代Notepad++的首选工具

    原生js随机图片拖拽排序代码.zip

    原生js随机图片拖拽排序代码.zip

    更快、更好、更稳定的Redis桌面(GUI)管理客户端,兼容Windows、Mac、Linux,性能出众,轻松加载海量键值

    更快、更好、更稳定的Redis桌面(GUI)管理客户端,兼容Windows、Mac、Linux,性能出众,轻松加载海量键值

Global site tag (gtag.js) - Google Analytics