[Swift]LeetCode307.区域和检索-数组可修改|RangeSumQuery-Mutable

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10247014.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 sumRangefunction is distributed evenly.

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

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

示例:

Given nums = [1, 3, 5]

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

说明:

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

192ms

  1 class NumArray {
  2     private class Node {
  3         var val: Int
  4         var sum: Int
  5         var count: Int
  6         var left: Node?, right: Node?
  7         init(val: Int, left: Node?, right: Node?) {
  8             self.val = val
  9             sum = val
 10             count = 1
 11             if let left = left {
 12                 self.left = left
 13                 sum += left.sum
 14                 count += left.count
 15             }    
 16             if let right = right {
 17                 self.right = right
 18                 sum += right.sum
 19                 count += right.count
 20             }    
 21         }
 22     }
 23 
 24     private var root: Node?
 25 
 26     init(_ nums: [Int]) {
 27         func makeTree(li: Int, ui: Int) -> Node? {
 28             if li <= ui {
 29                 let mid = li + (ui - li) / 2
 30                 let left = makeTree(li: li, ui: mid - 1)
 31                 let right = makeTree(li: mid + 1, ui: ui)
 32                 return Node(val: nums[mid], left: left, right: right)
 33             }
 34             return nil
 35         }
 36         root = makeTree(li: 0, ui: nums.count - 1)
 37     }
 38 
 39     func update(_ i: Int, _ val: Int) {
 40         if let root = root {
 41             update(node: root, i: i, val: val)
 42         }
 43     }
 44 
 45     private func update(node: Node, i: Int, val: Int) {
 46         if let left = node.left, i < left.count {
 47             let prevLeftSum = left.sum
 48             update(node: left, i: i, val: val)
 49             node.sum = node.sum - prevLeftSum + left.sum
 50         } else if i == (node.left?.count ?? 0) {
 51             node.sum = node.sum - node.val + val
 52             node.val = val
 53         } else if let right = node.right {
 54             let prevRightSum = right.sum
 55             update(node: right, i: i - (node.left?.count ?? 0) - 1, val: val)
 56             node.sum = node.sum - prevRightSum + right.sum
 57         }            
 58     }
 59 
 60     func sumRange(_ i: Int, _ j: Int) -> Int {
 61         if let root = root {
 62             return sum(node: root, count: j + 1) - sum(node: root, count: i)
 63         }
 64         return 0
 65     }
 66 
 67     private func sum(node: Node, count: Int) -> Int {
 68         if count == node.count {
 69             return node.sum
 70         }
 71 
 72         var s = 0
 73         var c = count
 74         if c > 0, let left = node.left {
 75             let lc = min(count, left.count)
 76             s += sum(node: left, count: lc)
 77             c -= lc
 78         }
 79         if c > 0 {
 80             s += node.val
 81             c -= 1
 82         }
 83         if c > 0, let right = node.right {
 84             s += sum(node: right, count: c)
 85         }
 86         return s
 87     }
 88 
 89     func inOrderPrint() {
 90         inOrderPrint(node: root)
 91         print()
 92     }
 93 
 94     private func inOrderPrint(node: Node?) {
 95         if let node = node {
 96             inOrderPrint(node: node.left)
 97             print((node.val, node.count, node.sum), terminator: " ")
 98             inOrderPrint(node: node.right)
 99         }
100     }
101 }

412ms

 1 class NumArray {
 2 
 3     var tree : [Int]
 4     var size : Int
 5    
 6     
 7     init(_ nums: [Int]) {
 8         size = nums.count
 9         tree = Array(repeating: 0, count: size << 2)
10         
11         if size != 0 {
12             build(1, size, 1, nums)
13         }
14         
15     }
16     
17     func build(_ l :Int, _ r : Int, _ rt : Int, _ nums : [Int]){
18         if l == r {
19             tree[rt] = nums[l-1]
20             return
21         }
22         
23         let m = (l + r) >> 1
24         build(l, m, rt<<1, nums)
25         build(m+1, r, rt<<1|1, nums)
26         pushup(rt)
27     }
28     
29     func pushup(_ rt : Int) {
30         tree[rt] = tree[rt<<1] + tree[rt << 1|1]
31     }
32     
33     func update(_ p : Int, _ val : Int, _ l : Int, _ r : Int, _ rt : Int){
34         if l == r {
35             tree[rt] = val
36             return
37         }
38         
39         let m = (l + r) >> 1
40         if p <= m {
41             update(p, val, l, m, rt << 1)
42         }else {
43             update(p, val, m+1, r, rt << 1 | 1)
44         }
45         
46         pushup(rt)
47     }
48     
49     func query(_ L : Int, _ R : Int, _ l : Int, _ r : Int, _ rt : Int) -> Int {
50         if L <= l && r <= R {
51             return tree[rt]
52         }
53         
54         let m = (l + r) >> 1
55         var ans = 0
56         if L <= m {
57             ans += query(L, R, l, m, rt<<1)
58         }
59         if R >= m+1 {
60             ans += query(L, R, m+1, r, rt << 1|1)
61         }
62         
63         return ans
64     }
65     
66     func update(_ i: Int, _ val: Int) {
67         update(i+1, val, 1, size, 1)
68 
69         
70     }
71     
72     func sumRange(_ i: Int, _ j: Int) -> Int {
73         return query(i+1, j+1, 1, size, 1)
74     }
75 }
76 
77 /**
78  * Your NumArray object will be instantiated and called as such:
79  * let obj = NumArray(nums)
80  * obj.update(i, val)
81  * let ret_2: Int = obj.sumRange(i, j)
82  */

2580ms

 1 class NumArray {
 2 
 3  var _nums : [Int]
 4     var sums : [Int]
 5     var changes : [Int : Int]
 6     
 7     init(_ nums: [Int]) {
 8         _nums = nums
 9         sums = nums
10         changes = [Int : Int]()
11         
12         if nums.isEmpty {
13             return
14         }
15         
16         for i in 1..<nums.count {
17             sums[i] += sums[i-1]
18         }
19         
20     }
21     
22     func update(_ i: Int, _ val: Int) {
23         if i >= _nums.count {
24             return
25         }
26         let c = val - _nums[i]
27         _nums[i] = val
28         if changes[i] != nil {
29             changes[i]! += c
30         }else {
31             changes[i] = c
32         }
33         
34         if !_nums.isEmpty && changes.count > _nums.count / 2 {
35             sums = _nums
36             for i in 1..<_nums.count {
37                 sums[i] += sums[i-1]
38             }
39             changes.removeAll()
40         }
41 
42         
43     }
44     
45     func sumRange(_ i: Int, _ j: Int) -> Int {
46         var res = sums[j]
47         if i > 0 {
48             res -= sums[i-1]
49         }
50         for dic in changes {
51             if dic.key <= j && dic.key >= i {
52                 res += dic.value
53             }
54         }
55         return res
56     }
57 }
58 
59 /**
60  * Your NumArray object will be instantiated and called as such:
61  * let obj = NumArray(nums)
62  * obj.update(i, val)
63  * let ret_2: Int = obj.sumRange(i, j)
64  */
65

4152ms

 1 class NumArray {
 2     
 3     private var sums: [Int] = []
 4     private var nums: [Int] = []
 5 
 6     init(_ nums: [Int]) {
 7         guard !nums.isEmpty else {
 8             return
 9         }
10         
11         var sums = Array(repeating: 0, count: nums.count)
12         sums[0] = nums[0]
13         for index in 1..<nums.count {
14             let num = nums[index]
15             sums[index] = sums[index - 1] + num
16         }
17 
18         self.sums = sums
19         self.nums = nums
20     }
21     
22     func update(_ i: Int, _ val: Int) {
23         guard i < nums.count else {
24             return
25         }
26         
27         let offset = val - nums[i]
28         guard offset != 0 else {
29             return
30         }
31         
32         for index in i..<nums.count {
33             sums[index] += offset
34         }
35         
36         nums[i] = val
37     }
38     
39     func sumRange(_ i: Int, _ j: Int) -> Int {
40         if i == 0 {
41             return sums[j]
42         } else {
43             return sums[j] - sums[i - 1]
44         }
45     }
46 }
47 
48 /**
49  * Your NumArray object will be instantiated and called as such:
50  * let obj = NumArray(nums)
51  * obj.update(i, val)
52  * let ret_2: Int = obj.sumRange(i, j)
53  */

4724ms

 1 class NumArray {
 2 
 3     var nums: [Int]
 4     var sumArray = [Int]()
 5     
 6     init(_ nums: [Int]) {
 7         self.nums = nums
 8         sumArray = nums
 9         if nums.count > 1 {
10             for i in 1 ..< nums.count {
11                 sumArray[i] = sumArray[i - 1] + nums[i]
12             }
13         }
14     }
15     
16     func update(_ i: Int, _ val: Int) {
17         let diff = val - nums[i]
18         self.nums[i] = val
19         for j in i ..< nums.count {
20             sumArray[j] += diff
21         }
22     }
23     
24     func sumRange(_ i: Int, _ j: Int) -> Int {
25         if i == 0 {
26             return sumArray[j]
27         } else {
28             return sumArray[j] - sumArray[i - 1]    
29         }
30         
31     }
32 }
33 
34 /**
35  * Your NumArray object will be instantiated and called as such:
36  * let obj = NumArray(nums)
37  * obj.update(i, val)
38  * let ret_2: Int = obj.sumRange(i, j)
39  */
40