`
mabusyao
  • 浏览: 252610 次
  • 性别: 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数组双指针算法求和问题LeetCode2sum3sum4sum含代码

    在编程领域,数组双指针算法是一种非常常见且高效的解决问题的方法,尤其在处理与数组元素求和相关的题目时。本文将深入探讨如何使用Python实现双指针算法来解决LeetCode中的2sum、3sum和4sum问题,并提供相关代码...

    文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码

    双指针算法是一种常见的数组或链表处理技巧,主要用于查找满足特定条件的元素组合。该方法通过维护两个指向不同位置的指针来简化搜索过程,提高效率。通常一个指针从数组头部开始移动,另一个从尾部开始移动,根据...

    C++第4章_数组与指针(C++课件,中南大学)

    在C++编程语言中,数组和指针是两个非常重要的概念,它们在处理...总的来说,数组和指针是C++中基础且强大的工具,它们在处理数据、优化代码性能和实现复杂算法时起着核心作用。理解这些概念对于掌握C++编程至关重要。

    C++习题 6数组与指针

    ### C++习题 6数组与指针知识点详解 #### 一、基本概念与基础知识自测题解析 ##### 5.1 填充题 **5.1.1 数组定义时有三个要素:** - **数组名**:数组的名字,用来标识这个数组。 - **数组元素的类型**:数组中...

    数组与指针详解

    数组和指针是C/C++编程语言中的两个核心概念,它们在程序设计中扮演着至关重要的角色。数组是一组相同类型的元素集合,而指针则是存储内存地址的变量,可以用来间接访问这些元素。理解它们之间的关系对于编写高效且...

    算法 数组 双指针移除相同元素

    适用人群:刚接触数据结构与算法 难度:较简单 方法:多看多练,多思考 语言:java

    C语言经典指针与数组ppt

    - **冒泡排序**:数组在排序算法中也发挥重要作用,如冒泡排序,通过数组元素间的比较和交换实现排序。 掌握数组和指针的使用对于理解和编写高效的C语言程序至关重要。在实际编程中,理解它们的工作原理和相互作用...

    C语言程序—指针算法分析.pdf

    同时,也应该教会学生如何使用指针算法来操作数组,包括如何通过指针算法遍历数组元素、如何实现二维数组指针算法的移动等。 在C语言教学中,教师不仅要向学生传授指针算法的基础知识,还要引导学生学会在复杂数据...

    双指针算法应用方式介绍

    双指针算法是一种在计算机科学和编程中广泛使用的高效算法,尤其在处理数组或链表等线性数据结构的问题上。这种算法的核心在于利用两个指针同时遍历数据,通过它们之间的相对移动来解决问题,从而大大减少计算的时间...

    数组与排序算法:从基础到进阶

    算法竞赛参与者:准备算法竞赛,需要掌握各种排序算法和双指针、滑动窗口等高级技巧。 计算机科学学生:正在学习数据结构和算法课程,需要深入理解数组操作和排序原理。 应用场景: 面试准备:掌握数组和排序算法是...

    c语言数组与指针

    在编程世界中,C语言是一种基础且强大的编程语言,它以简洁、高效著称,而数组和指针是C语言中的核心概念。本教程将深入探讨数组和指针的使用,帮助你掌握这两个关键概念。 首先,我们来讨论“数组”。数组在C语言...

    数组倒置经典算法

    - **两指针法**:设置两个指针,一个指向数组起始位置,另一个指向末尾位置,然后交换这两个位置上的元素,并逐步向数组中心移动,直到两个指针相遇或交错。 - **循环法**:创建一个新的数组,按照逆序的方式将原...

    C语言学习数组与指针

    在C语言中,数组和指针是两个非常基础且重要的概念。数组是一种构造数据类型,它是由相同类型的多个变量组成的集合。数组中的每个元素可以通过数组名和一个下标来访问,下标通常从0开始。一维数组是最简单的形式,...

    指针指针数组多级指针动态指针PPT学习教案.pptx

    在上面的示例中,我们使用了指针数组和多级指针来实现字符串排序算法。 首先,我们定义了一个字符指针数组:char \*ptr[N] = {"Pascal","Basic","Fortran","Java","Visual C"};然后,我们使用了双重循环来实现字符...

    双指针算法 使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的

    双指针算法的适用场景广泛,不仅限于上述例子,还包括寻找数组中的最长回文子串、找到有序数组中的中位数、解决二维数组中的最短路径问题等。在实际应用中,双指针能帮助我们更高效地遍历数据结构,解决问题。 在...

    双指针算法实现有序数组地合并

    算法没想象中那么难,只要系统学过,算法几乎就等同与脑筋急转弯。 这次,利用双指针算法优雅地实现有序数组地合并。 看完后,你会觉得原来算法这么简单。

    双指针算法基本原理和实践.pdf

    双指针算法是一种在编程中常见的高效解决策略,它通过设置两个或更多指针来遍历数据结构(如数组或链表),以实现特定的逻辑操作。这种算法通常用于查找、排序、合并等问题,能够有效地减少时间复杂度,提高代码执行...

    双指针算法,算法练习代码练习

    双指针算法是一种在编程和算法设计中广泛使用的技巧,主要应用于数组或链表等线性数据结构。这种算法的核心思想是通过维护两个指针,分别从数据结构的两端或某一特定位置开始,以不同的速度或方向进行遍历,从而解决...

    C语言程序设计第4章数组和指针

    在C语言中,数组和指针是编程时非常重要的概念,尤其在处理大量数据或实现高效算法时。在第四章“数组和指针”中,我们主要探讨了以下几个知识点: 1. **数组的概念**: 数组是一组相同类型的变量,它们按照下标...

Global site tag (gtag.js) - Google Analytics