leetcode笔记:Range Sum Query – Mutable【必发娱乐手机版】

LeetCode 303 Range Sum Query – Immutable(范围总和查询-永久不变)(*)

leetcode笔记:Range Sum Query – Mutable

一. 题目描述

Given an integer array nums, find the sum of the elements between
indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at
index i to val.

Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is
distributed evenly.

二. 题目分析

题目在Range Sum Query –
Immutable一题的基础上增加的难度,要求在输入数组nums后,能够修改数组的元素,每次只修改一个元素。同样要实现求数组的某个区间和的功能。

如果在一题的做法上稍加改进,是可以实现功能的,但是会超时。

这时阅读了一些文章后才发现原来经典的做法(包括前一题)是使用树状数组来维护这个数组nums,其插入和查询都能做到O(logn)的复杂度,十分巧妙。

三. 示例代码

// 超时
class NumArray {
public:
    NumArray(vector &nums) {
        if (nums.empty()) return;
        else
        {
            sums.push_back(nums[0]);
            //求得给定数列长度
            int len = nums.size();
            for (int i = 1; i < len; ++i)
                sums.push_back(sums[i - 1] + nums[i]);
        }
    }

    void update(int i, int val) {
        for (int k = i; k < nums.size(); ++k)
            sums[k] += (val - nums[i]);
        nums[i] = val;
    }

    int sumRange(int i, int j) {
        return sums[j] - sums[i - 1];
    }

private:
    vector nums;
    //存储数列和
    vector sums;
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

// 使用树状数组实现的代码AC,复杂度为O(logn)
class NumArray {
private:
    vector c;
    vector m_nums;
public:
    NumArray(vector &nums) {
        c.resize(nums.size() + 1);
        m_nums = nums;
        for (int i = 0; i < nums.size(); i++){
            add(i + 1, nums[i]);
        }
    }

    int lowbit(int pos){
        return pos&(-pos);
    }

    void add(int pos, int value){
        while (pos < c.size()){
            c[pos] += value;
            pos += lowbit(pos);
        }
    }
    int sum(int pos){
        int res = 0;
        while (pos > 0){
            res += c[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    void update(int i, int val) {
        int ori = m_nums[i];
        int delta = val - ori;
        m_nums[i] = val;
        add(i + 1, delta);
    }

    int sumRange(int i, int j) {
        return sum(j + 1) - sum(i);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

四. 小结

之前只是听过,这是第一次使用树状数组,这是维护数组的一个很好的思想,需要深入学习!

http://www.bkjia.com/cjjc/1094178.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1094178.htmlTechArticleleetcode笔记:Range Sum Query – Mutable 一.
题目描述 Given an integer array nums , find the sum of the elements
between indices i and j (i j) , inclusive. The update(i, val…

代码

class NumArray {
public:
    vector rangeSum;

    NumArray(vector &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.push_back(sum);
        }
    }

    int sumRange(int i, int j) {
        return rangeSum[j] - rangeSum[i - 1];
    }
};

http://www.bkjia.com/cjjc/1097708.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1097708.htmlTechArticleLeetCode 303 Range Sum Query –
Immutable(范围总和查询-永久不变)(*) 翻译
给定一个整型数组nums,找出在索引i到j(i小于等于j)之间(包括i和…

分析

一开始我还以为这个题有多简单呢,就写了下面这个代码:

class NumArray {
public:
    vector numArray;
    NumArray(vector &nums) {
        numArray = nums;
    }
    int sumRange(int i, int j) {
        int sum = 0;
        while (i < j) {
            sum += numArray[i++];
        }
        return sum;
    }
};

因为不知道需要构造函数干嘛,所以硬生生的加了这么一句进去,其实完全没用。功能是实现了,但是面对题目变态的测试用例,果然还是崩了。

至于题目测试用例有多变态,数据来说话:一共214513个字符,其中包括了nums的数据,也包括了函数调用,nums的长度没去算,但是sumRange函数的调用次数高达10000次。

看到这个测试用例,就明白要针对函数调用做优化,一个不错的办法是将所有的返回的值:

从0到1的所有元素之和,
从0到2的所有元素之和,
从0到10000的所有元素之和,
………………

然后计算i和j之间所有元素之和的时候,(因为包含了i和j),也就是求从0到j的所有元素之和减去从0到i-1的所有元素之和。

所以代码就如下所示了,但是时间上还是使用了624ms叻。

class NumArray {
public:
    map rangeSum;
    NumArray(vector &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.insert(pair(i, sum));
        }
    }

    int sumRange(int i, int j) {
        return rangeSum[j] - rangeSum[i - 1];
    }
};

虽然对底层的具体实现不是很了解,但因为有索引,所以我自觉用vector的话查找其值来跟快速;而且添加值也更加快速,因为只是一个值而不用是键值对。

具体代码如下:

翻译

给定一个整型数组nums,找出在索引i到j(i小于等于j)之间(包括i和j)的所有元素之和。

例如:
给定nums = [-2,0,3,-5,2,-1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

批注:
你可以假定这个数组不会改变。
这里会有很多次对sumRange函数的调用。

原文

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.