[Swift]LeetCode528.按权重随机选择|RandomPickwithWeight

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

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

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

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

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

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

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.

Example 1:

Input: 
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.

给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

说明:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次

示例1:

输入: 
["Solution","pickIndex"]
[[[1]],[]]
输出: [null,0]

示例2:

输入: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出: [null,0,1,1,1,0]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

704ms

 1 class Solution {
 2     var total: Int
 3     var pTotal: [Int]
 4     init(_ w: [Int]) {
 5         total = 0
 6         pTotal = [Int]()
 7         for x in w{
 8             total += x
 9             pTotal.append(total)
10         }
11     }
12     
13     func pickIndex() -> Int {
14         let index = Int.random(in: 0..<total)
15         var lo = 0, hi = pTotal.count-1
16         while lo != hi{
17             let mid = (lo+hi)/2
18             if pTotal[mid] <= index{
19                 lo = mid + 1
20             }else{
21                 hi = mid
22             }
23         }
24         return lo
25     }
26 }
27 
28 /**
29  * Your Solution object will be instantiated and called as such:
30  * let obj = Solution(w)
31  * let ret_1: Int = obj.pickIndex()
32  */

720ms

 1 class Solution {
 2 
 3     let nums:[Int]
 4     
 5     init(_ w: [Int]) {
 6         var sum = 0
 7         var result = [Int]()
 8         w.forEach {
 9             sum += $0
10             result.append(sum)
11         }
12         nums = result
13     }
14     
15     func pickIndex() -> Int {
16        let sum = nums.last!
17        let num = Int.random(in: 0..<sum) % sum
18         var left = 0
19         var right = nums.count - 1
20         while left + 1 < right {
21             let mid = left + (right - left) / 2
22             if nums[mid] > num {
23                 right = mid
24             } else {
25                 left = mid
26             }
27         }
28         
29         if nums[left] > num {
30             return left
31         } else {
32             return right
33         }
34     }
35 }

752ms

 1 class Solution {
 2     
 3     let w: [Int]
 4     let sum: Int
 5 
 6     init(_ w: [Int]) {
 7         sum = w.reduce(0, +)
 8         self.w = w.reduce([Int]()){ 
 9             let n = ($0.last ?? 0) + $1
10             return $0 + [n]
11         }
12     }
13     
14     func pickIndex() -> Int {
15         let random = Int.random(in: 0...sum-1)
16         return searchInsert(w, random)
17     }
18     
19     func searchInsert(_ nums: [Int], _ target: Int) -> Int {
20         var low = 0
21         var high = nums.count-1
22         while low <= high {
23             let middle = (low + high) / 2
24             if nums[middle] == target {
25                 return middle+1
26             } else if nums[middle] > target {
27                 high = middle - 1
28             } else {
29                 low = middle + 1
30             }
31         }
32         return low
33     }
34 }

772ms

 1 class Solution {
 2     
 3     var sum: [Int]
 4 
 5     init(_ w: [Int]) {
 6         sum = [Int]()
 7         sum.append(w[0])
 8         for i in 1..<w.count {
 9             sum.append(sum[i-1] + w[i])
10         }
11     }
12     
13     func pickIndex() -> Int {
14         let value = Int.random(in: 1...sum.last!)
15         return bSearch(value, 0, sum.count - 1)
16     }
17     
18     private func bSearch(_ value: Int, _ start: Int, _ end: Int) -> Int {
19         let mid = start + (end - start) / 2
20         if sum[mid] >= value && (start == mid || sum[mid - 1] < value) { return mid }
21         if sum[mid] < value {
22             return bSearch(value, mid + 1, end)
23         }
24         return bSearch(value, start, mid - 1)
25     }
26 }

784ms

 1 class Solution {
 2 
 3     private let accSum: [Int]
 4 
 5     init(_ w: [Int]) {
 6         self.accSum = w.reduce([]) { $0 + [($0.last ?? 0) + $1]}
 7     }
 8     
 9     func pickIndex() -> Int {
10         let num = Int.random(in: 1 ... accSum.last!)  
11         var (left, right) = (0, accSum.count - 1)
12         while left < right {
13             let mid = left + (right - left) / 2
14             if accSum[mid] == num {
15                 return mid
16             } else if accSum[mid] < num {
17                 left = mid + 1
18             } else {
19                 right = mid
20             }
21         }
22 
23         return left
24     }
25 }

Runtime: 976 ms

Memory Usage: 19.9 MB

 1 class Solution {
 2     var sum:[Int]
 3 
 4     init(_ w: [Int]) {
 5         sum = w
 6         for i in 1..<w.count
 7         {
 8             sum[i] += sum[i - 1]
 9         }        
10     }
11     
12     func pickIndex() -> Int {
13         var x:Int = Int.random(in:0..<sum.last!)
14         var left:Int = 0
15         var right:Int = sum.count - 1  
16         var mid:Int = 0
17         while (left < right)
18         {
19             mid = left + (right - left) / 2
20             if sum[mid] <= x
21             {
22                 left = mid + 1
23             }
24             else 
25             {
26                 right = mid
27             }            
28         }        
29         return right   
30     }
31 }
32 
33 /**
34  * Your Solution object will be instantiated and called as such:
35  * let obj = Solution(w)
36  * let ret_1: Int = obj.pickIndex()
37  */
38