Leetcode 307:区域和检索-数组不可变(超详细解决方案!!!)
in leetcode with 0 comment

Leetcode 307:区域和检索-数组不可变(超详细解决方案!!!)

in leetcode with 0 comment

给定一个整数数组 nums,求出数组从索引 ij (ij) 范围内元素的总和,包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

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

说明:

  1. 数组仅可以在 update 函数下进行修改。
  2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

解题思路

这是之前问题Leetcode 303:区域和检索-数组不可变(超详细解决方案!!!)的提高,我们还是按照之前的方式来解决,如果index: i更新的话,我们就更新[i:]的累加结果。

from itertools import accumulate
class NumArray:
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.data = [0] + nums
        self.nums = list(accumulate(self.data))

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        self.data[i+1] = val
        self.nums = self.nums[:i] + list(accumulate([self.nums[i]] + self.data[i+1:]))

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.nums[j+1] - self.nums[i]

但是这种做法超时了,有什么更好的做法吗?由于这是一个区域更新的问题,所以我想到了通过线段树来解决这个问题。一个简化版的线段树

class SegmentTree:
    def __init__(self, data):
        self.data = data
        self.tree = [0]*4*len(data)
        self.buildSegmentTree(0, 0, len(data) - 1)
        
    def buildSegmentTree(self, treeIndex, l, r):
        if l == r:
            self.tree[treeIndex] = self.data[l]
            return
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        self.buildSegmentTree(lc, l, mid)
        self.buildSegmentTree(rc, mid + 1, r)
        self.tree[treeIndex] = self.tree[lc] + self.tree[rc]
        
    def update(self, index, val):
        self.data[index] = val
        self._update(0, 0, len(self.data)-1, index, val)
        
    def _update(self, treeIndex, l, r, index, val):
        if l == r:
            self.tree[treeIndex] = val
            return 
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        if index > mid:
            self._update(rc, mid+1, r, index, val)
        else:
            self._update(lc, l, mid, index, val)
            
        self.tree[treeIndex] = self.tree[lc] + self.tree[rc]
        
    def sumRange(self, i, j):
        return self._sumRange(0, 0, len(self.data)-1, i, j)
        
    def _sumRange(self, treeIndex, l, r, ql, qr):
        if l == ql and r == qr:
            return self.tree[treeIndex]
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        if ql > mid:
            return self._sumRange(rc, mid + 1, r, ql, qr)
        else:
            return self._sumRange(lc, l, mid, ql, qr)
        
        left = self._sumRange(lc, l, mid, ql, mid)
        right = self._sumRange(rc, mid + 1, r, mid + 1, qr)
        return left + right

我们将上述的写法应用到我们的问题中。

class NumArray:
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.data = nums
        self.tree = [0]*4*len(nums)
        if self.data:
            self.buildSegmentTree(0, 0, len(nums) - 1)
        
    def buildSegmentTree(self, treeIndex, l, r):
        if l == r:
            self.tree[treeIndex] = self.data[l]
            return
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        self.buildSegmentTree(lc, l, mid)
        self.buildSegmentTree(rc, mid + 1, r)
        self.tree[treeIndex] = self.tree[lc] + self.tree[rc]

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        self.data[i] = val
        self._update(0, 0, len(self.data)-1, i, val)
        
    def _update(self, treeIndex, l, r, index, val):
        if l == r:
            self.tree[treeIndex] = val
            return 
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        if index > mid:
            self._update(rc, mid+1, r, index, val)
        else:
            self._update(lc, l, mid, index, val)
            
        self.tree[treeIndex] = self.tree[lc] + self.tree[rc]

    def sumRange(self, i, j):
        return self._sumRange(0, 0, len(self.data)-1, i, j)
        
    def _sumRange(self, treeIndex, l, r, ql, qr):
        if l == ql and r == qr:
            return self.tree[treeIndex]
        
        lc, rc = 2*treeIndex+1, 2*(treeIndex + 1)
        mid = (l + r) // 2
        if ql > mid:
            return self._sumRange(rc, mid + 1, r, ql, qr)
        elif qr <= mid:
            return self._sumRange(lc, l, mid, ql, qr)
        
        left = self._sumRange(lc, l, mid, ql, mid)
        right = self._sumRange(rc, mid + 1, r, mid + 1, qr)
        return left + right

我们获得了accept,虽然速度不是很快,但是确实是一个非常好的解法。这个问题还有一个比较好的解法就是树状数组

class NumArray:
    def __init__(self, nums: 'List[int]'):
        self.nums = nums
        self.tree = FenwickTree(nums)
        for i in range(len(nums)):
            self.tree.update(i+1, nums[i])

    def update(self, i: 'int', val: 'int') -> 'None':
        self.tree.update(i+1, val - self.nums[i])
        self.nums[i] = val

    def sumRange(self, i: 'int', j: 'int') -> 'int':
        return self.tree.query(j+1) - self.tree.query(i)
    
class FenwickTree:
    def __init__(self, nums):
        self.nums = [0]*(len(nums) + 1)
        
    def update(self, i, delta):
        while i < len(self.nums):
            self.nums[i] += delta
            i += self.lowbit(i)
    
    def query(self, i):
        res = 0
        while i:
            res += self.nums[i]
            i -= self.lowbit(i)
        return res
            
    def lowbit(self, x):
        return x & (-x)

我们将上述的写法应用到我们的问题中。

class NumArray:
    def __init__(self, nums: 'List[int]'):
        self.nums = nums
        self.tree = [0]*(len(nums) + 1)
        for i in range(len(nums)):
            self._update(i+1, nums[i])
            
    def _update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)
    
    def query(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= self.lowbit(i)
        return res
            
    def lowbit(self, x):
        return x & (-x)

    def update(self, i: 'int', val: 'int') -> 'None':
        self._update(i+1, val - self.nums[i])
        self.nums[i] = val

    def sumRange(self, i: 'int', j: 'int') -> 'int':
        return self.query(j+1) - self.query(i)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses