专栏首页小小挖掘机求解连续子数组和全解析-常规解法VS树状数组!

求解连续子数组和全解析-常规解法VS树状数组!

本文将介绍几求解数组前缀和和连续子数组和的三种方法,分别是遍历法、辅助数组法、树状数组法。

先来定义我们的问题,假设数组为A=[a[0],a[1],a[2],...,a[n]],我们想要求解A[from:to]的和,即求解a[from]+a[from+1]+....+a[to]。

1、遍历法

遍历法很简单,即从from的位置循环到to的位置,将元素加起来,代码如下:

package RangeSum;

public class Traversal {


    public static int traversal(int[] arr,int start,int end){
        int res = 0;
        if(start < 0 || start >arr.length || end > arr.length){
            System.out.println("index error");
            return -999;
        }
        for(int i=start;i<=end;i++){
            res += arr[i];
        }
        return res;
    }

    public static void main(String[] args){
        int[] arr = {5,3,2,8,7,10,13,6};
        //2 + 8 + 7 + 10 + 13 = 40
        System.out.println(traversal(arr,2,6));
    }
}

遍历法很简单,若区间长度为m,那么求解的时间复杂度为O(m),空间复杂度为O(1)。

遍历法求解简单,单次求解的情况下非常适用。但是当我们需要频繁求解连续子数组和时,就不是那么适用了,这时候,我们便有了辅助数组法。

2、辅助数组法

辅助数组法比较适用于频繁求解连续子数组和的情况,此时,我们增加辅助数组s,s[m]代表0到m的元素和,代码如下:

package RangeSum;

public class AuxiliaryArr {

    public static int[] auxiliary(int[] arr){
        if(arr == null || arr.length <= 0)
            return null;
        int[] aux = new int[arr.length];
        aux[0] = arr[0];
        for(int i=1;i<arr.length;i++){
            aux[i] = aux[i-1] + arr[i];
        }
        return aux;
    }

    public static int sumRange(int[] arr,int start,int end){
        if(start < 0 || start >arr.length || end > arr.length){
            System.out.println("index error");
            return -999;
        }
        else if(start == 0){
            return arr[end];
        }
        else{
            return arr[end] - arr[start-1];
        }

    }

    public static void main(String[] args){
        int[] arr = {5,3,2,8,7,10,13,6};
        //2 + 8 + 7 + 10 + 13 = 40
        int[] auxiliaryArr = auxiliary(arr);
        System.out.println(sumRange(auxiliaryArr,2,6));
    }
}

辅助数组法的建数组时间复杂度时O(n),空间复杂度为O(n),当频繁求解子数组和时,求和复杂度为O(1)。

但是,当我们回频繁修改数组a时,辅助数组法也不是那么适用,因为修改数组a,辅助数组s也是要更新的,最坏的情况下,我们更新a[0],那么辅助数组的每一个元素都需要修改。如果实时对数组a进行M次修改和求和,那么最坏情况下的时间复杂度时O(M * n)。

这种情况下,有没有更好的解决方法呢!本文的重头戏,树状数组法就要出马了,如果实时对数组a进行M次修改和求和,树状数组的时间复杂度可以达到O(M * logn)。我们一起来看一下。

3、树状数组法

假设我们有数组A={1,2,3,4,5,6,7,8},我们首先构造一颗二叉树,如下图所示:

随后进行变形,其实什么都没做,只是为了后面看的清晰:

随后,我们定义树状数组C:

可以看到,树状数组中根节点和所有的左子节点都被赋予了相应的值,而且:

C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

怎么知道左子节点在树状数组中的索引呢?其实就是从叶子结点开始往上找,比如C[4],从叶子结点的第四个,由于它是右子节点,所以向上找父节点,发现父节点仍然是右子节点,所以再往上找,发现此时父节点为左子节点,停止寻找。

上面树状数组中的元素,分别是原数组中连续子数组求和得到的,那么怎么知道是哪些元素的求和呢?可以看到,C[m]对应的连续子数组的末尾元素一定是A[m],关键是如何找到起始的元素。

我们首先将十进制数字转换为二进制表示,看能不能发现一些规律:

1=(001)      C[1]=A[1];
2=(010)      C[2]=A[1]+A[2];
3=(011)      C[3]=A[3];
4=(100)      C[4]=A[1]+A[2]+A[3]+A[4];
5=(101)      C[5]=A[5];
6=(110)      C[6]=A[5]+A[6];
7=(111)      C[7]=A[7];
8=(1000)    C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

结合树来看一下:

发现规律了没: 1、最后一个1出现在末位,即二进制末尾有0个0,C[m]是一个元素的和,即C[m]=A[m] 2、最后一个1出现在倒数第二位,即二进制末尾有1个0,C[m]是两个元素的和,即C[m] = A[m] + A[m-1] 3、最后一个1出现在倒数第三位,即二进制末尾有2个0,C[m]是4个元素的和.... 4、最后一个1出现在倒数第k+1位,即二进制末尾有k个0,C[m]是2^k个元素的和。

因此,我们可以得到计算公式,k为m的二进制中从最低位到高位连续零的长度:

C[m]=A[m-2^k+1]+A[to-2^k+2]+......A[m];

好了,回到我们最开始的问题,如何在原数组更新频繁和多次求解的情况下,快速解决连续子数组求和的问题呢?

那么求解子数组和的问题可以转化为如下的递归形式:

sumRange[from:to] = A[from] + A[from + 1] +..+A[to] = sum[from:to - 2^k] + C[to]

C[to] = A[to-2^k+1]+A[to-2^k+2]+......A[to];

好了,来看下代码实现吧。

我们首先定义一个lowbit函数,lowbit(m)=2^k:

public static int lowbit(int t){        return t & (-t);}

随后我们定义两个数组,分别是原数组和树状数组,这里,我们在初始化的时候,在传入的数组前面增加了一个元素,这样,就跟我们上面的讲解保持一致,即数组的元素下标从1开始:

int[] arr = null;
int[] bitArr = null;
int n = 0;

public BIT(int[] arr){
    this.arr = new int[arr.length + 1];
    for(int i=0;i<arr.length;i++){
        this.arr[i+1] = arr[i];
    }
    this.n = arr.length;
    this.initBitArr();
}

public void initBitArr(){
    bitArr = new int[this.arr.length];
    for(int i=1;i<=this.arr.length;i++){
        this.update(i);
    }
}

在初始化树状数组时,我们使用了更新树状数组元素这个函数,更新的时间复杂度是O(logn),因为只需要从叶子结点开始,不断向上直到根节点即可:

public void update(int index){
    for(int i=index;i <=n ;i += lowbit(i)){
        this.bitArr[i] += this.arr[index];
    }
}

随后便是分段求和的函数:我们想要求原数组from到to位置的元素和,那么使用树状数组中的对应位置便是from+1到to+1位置,我们这里使用两段和相减得到最终结果,分别是[1,to+1],[1,from],这样,二者相减便是最终结果。

public int sum(int from1,int to1){
    int ans1 = 0;
    int ans2 = 0;
    int from = from1 + 1;
    int to = to1 + 1;
    for(int i=to;i>0;i-= lowbit(i)){
        ans1 += this.bitArr[i];
    }
    if(from1 > 0){
        for(int i=from-1;i>0;i-= lowbit(i)){
            ans2 += this.bitArr[i];
        }
    }
    return ans1-ans2;
}

完整的代码如下:

 
package RangeSum;

public class BIT {

    int[] arr = null;
    int[] bitArr = null;
    int n = 0;

    public BIT(int[] arr){
        this.arr = new int[arr.length + 1];
        for(int i=0;i<arr.length;i++){
            this.arr[i+1] = arr[i];
        }
        this.n = arr.length;
        this.initBitArr();
    }

    public void initBitArr(){
        bitArr = new int[this.arr.length];
        for(int i=1;i<=this.arr.length;i++){
            this.update(i);
        }
    }

    public void update(int index){
        for(int i=index;i <=n ;i += lowbit(i)){
            this.bitArr[i] += this.arr[index];
        }
    }

    public int sum(int from1,int to1){
        int ans1 = 0;
        int ans2 = 0;
        int from = from1 + 1;
        int to = to1 + 1;
        for(int i=to;i>0;i-= lowbit(i)){
            ans1 += this.bitArr[i];
        }
        if(from1 > 0){
            for(int i=from-1;i>0;i-= lowbit(i)){
                ans2 += this.bitArr[i];
            }
        }
        return ans1-ans2;
    }

    public static int lowbit(int t){
        return t & (-t);
    }


    public static void main(String[] args){
        int[] arr = {1,2,3,4,5,6,7,8};
        //System.out.println(traversal(arr,2,6));
        BIT bit = new BIT(arr);
        System.out.println(bit.sum(0,6));

    }
}

本文分享自微信公众号 - 小小挖掘机(wAIsjwj),作者:石晓文

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 各种排序算法的分析及java&python实现

    排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

    石晓文
  • 盘一盘 NumPy (上)

    Numpy 是 Python 专门处理高维数组 (high dimensional array) 的计算的包,每次使用它遇到问题都会它的官网 (www.num...

    石晓文
  • 一招解决4道leetcode hard题,动态规划在字符串匹配问题中的应用

    在做leetcode的时候,遇到hard题大家往往都觉得头疼,但其实,掌握方法,举一反三,hard题有时候我们也能想到好的思路,顺利攻破,今天我们就介绍一下动态...

    石晓文
  • java基础学习_基础语法(下)01_day05总结

    ============================================================================= ==...

    黑泽君
  • Java 语法(五):数组

    当然,一般情况下我们更喜欢使用第一种方式来声明一个数组,因为它将类型与变量名分开,优化了代码的可读性。刚刚我们只是声明了一个数组 a ,但是并没有将 a 初始化...

    山禾说
  • 【Java】04 数组

    初始化:   静态初始化:初始化时由程序员显式指定每个数组元素的初始值,由系统决定数组长度。   动态初始化:初始化时程序员只指定数组长度,由系统为数组元素...

    Demo_Null
  • 寻找数组中第二小的元素

    一觉睡到小时候
  • LeetCode刷题记录:剑指 Offer 10- I. 斐波那契数列

    解题思路: 根据输入的 n 声明一个数组,定义好数组的前两个元素(即第 0 项和第 1 项),从第三个元素开始遍历数组,使数组的每一个元素等于前两个元素之和。...

    英雄爱吃土豆片
  • [算法题] 荷兰国旗问题

    假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:

    CoderJed
  • 如何实现归并排序?

    划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。

    行百里er

扫码关注云+社区

领取腾讯云代金券