[Swift]LeetCode307. 区域和检索 - 数组可修改 | 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: Give

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) -> 9update(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,2) -> 8

说明:

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

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             return21         }22         23         let m = (l + r) >> 124         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,_ rt : Int){34         if l == r {35             tree[rt] = val36             return37         }38         39         let m = (l + r) >> 140         if p <= m {41             update(p,val,l,rt << 1)42         }else {43             update(p,m+1,rt << 1 | 1)44         }45         46         pushup(rt)47     }48     49     func query(_ L : Int,_ R : Int,_ rt : Int) -> Int {50         if L <= l && r <= R {51             return tree[rt]52         }53         54         let m = (l + r) >> 155         var ans = 056         if L <= m {57             ans += query(L,R,rt<<1)58         }59         if R >= m+1 {60             ans += query(L,rt << 1|1)61         }62         63         return ans64     }65     66     func update(_ i: Int,_ val: Int) {67         update(i+1,1,1)68 69         70     }71     72     func sumRange(_ i: Int,_ j: Int) -> Int {73         return query(i+1,j+1,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 = nums10         changes = [Int : Int]()11         12         if nums.isEmpty {13             return14         }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             return25         }26         let c = val - _nums[i]27         _nums[i] = val28         if changes[i] != nil {29             changes[i]! += c30         }else {31             changes[i] = c32         }33         34         if !_nums.isEmpty && changes.count > _nums.count / 2 {35             sums = _nums36             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.value53             }54         }55         return res56     }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] + num16         }17 18         self.sums = sums19         self.nums = nums20     }21     22     func update(_ i: Int,_ val: Int) {23         guard i < nums.count else {24             return25         }26         27         let offset = val - nums[i]28         guard offset != 0 else {29             return30         }31         32         for index in i..<nums.count {33             sums[index] += offset34         }35         36         nums[i] = val37     }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] = val19         for j in i ..< nums.count {20             sumArray[j] += diff21         }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  

总结

以上是内存溢出为你收集整理的[Swift]LeetCode307. 区域和检索 - 数组可修改 | Range Sum Query - Mutable全部内容，希望文章能够帮你解决[Swift]LeetCode307. 区域和检索 - 数组可修改 | Range Sum Query - Mutable所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。