• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode398.随机数索引|RandomPickIndex

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意:
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

792ms
 1 class Solution {
 2     var v:[Int] = [Int]()
 3 
 4     init(_ nums: [Int]) {
 5         v = nums
 6     }
 7     
 8     func pick(_ target: Int) -> Int {
 9         var cnt:Int = 0
10         var res:Int = -1
11         for i in 0..<v.count
12         {
13             if v[i] != target {continue}
14             cnt += 1
15             if Int.random(in: 0...Int.max) % cnt == 0 
16             {
17                 res = i
18             }
19         }
20         return res      
21     }
22 }
23 
24 /**
25  * Your Solution object will be instantiated and called as such:
26  * let obj = Solution(nums)
27  * let ret_1: Int = obj.pick(target)
28  */
29  

824ms

 1 class Solution {
 2 
 3     let nums: [Int]
 4     let numSize: Int
 5     
 6     init(_ nums: [Int]) {
 7         self.nums = nums
 8         numSize = nums.count
 9     }
10     
11     func pick(_ target: Int) -> Int {
12         for i in 0..<numSize {
13             let idx = Int.random(in: 0..<numSize-i) + i
14             if nums[idx] == target {
15                 return idx
16             }
17             if nums[i] == target {
18                 return i
19             }
20         }
21         
22         return 0
23     }
24 }

916ms

 1 class Solution {
 2     var map:[Int: [Int]] = [:]
 3     
 4     init(_ nums: [Int]) {
 5         map = [:]
 6         for i in 0 ..< nums.count {
 7             var array = map[nums[i]]
 8             if array == nil {
 9                 array = []
10             }
11             array!.append(i)
12             map[nums[i]] = array
13         }
14     }
15     
16     func pick(_ target: Int) -> Int {
17         if let array = map[target] {
18             let size = array.count
19             let r = Int.random(in: 0 ..< size)
20             return array[r]
21         }
22         return -1
23     }
24 }

940ms

 1 class Solution {
 2     var d: [Int: [Int]] = [:]
 3 
 4     init(_ nums: [Int]) {
 5         for (i, num) in nums.enumerated() {
 6             if let some = d[num] {
 7                 d[num] = some + [i]
 8             } else {
 9                 d[num] = [i]
10             }
11         }
12     }
13     
14     func pick(_ target: Int) -> Int {
15         let arr = d[target]!
16         var randI = Int.random(in: 0..<arr.count)
17         return arr[randI]
18     }
19 }

952ms

 1 class Solution {
 2     
 3     private let numsIndices: [Int: [Int]]
 4 
 5     init(_ nums: [Int]) {
 6         var idxMap = [Int: [Int]]()
 7         for (offset, num) in nums.enumerated() {
 8             if idxMap[num] == nil { idxMap[num] = [Int]() }
 9             idxMap[num]?.append(offset)
10         }
11         numsIndices = idxMap
12     }
13     
14     func pick(_ target: Int) -> Int {
15         return numsIndices[target]!.randomElement()!
16     }
17 }

1020ms

 1 class Solution {
 2 
 3     var mapping = [Int: [Int]]()//key is the number, value is the index array
 4     init(_ nums: [Int]) {
 5         for i in 0..<nums.count{
 6             if var indexArray = mapping[nums[i]]{
 7                 indexArray.append(i)
 8                 mapping[nums[i]] =  indexArray
 9             } else{
10                 mapping[nums[i]] = [i]
11             }
12         }
13     }
14     
15     func pick(_ target: Int) -> Int {
16         if let indexArray = mapping[target]{
17             return indexArray.randomElement()!
18         }
19         return -1      
20     }
21 }

1172ms

 1 class Solution {
 2     
 3     var nums: [Int]
 4     
 5     init(_ nums: [Int]) {
 6         self.nums = nums
 7     }
 8     
 9     func pick(_ target: Int) -> Int {
10         let array = self.nums.enumerated().shuffled()
11         for i in stride(from: 0, to: array.count, by: 1) {
12             if i >= array.count {
13                 return -1
14             }
15             if array[i].element == target {
16                 print(array[i].offset)
17                 return array[i].offset
18             }
19         }
20         return -1 
21     }
22 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift中类的构造函数&amp;析构函数发布时间:2022-07-13
下一篇:
swift4.0 YYModel进行数组转模型时, 转换的数据为nil发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap