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

[Swift]LeetCode911.在线选举|OnlineElection

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

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

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

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

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

In an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.  

Votes cast at time t will count towards our query.  In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input: [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
Output: [null,0,1,1,0,0,1]
Explanation: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Note:

  1. 1 <= persons.length = times.length <= 5000
  2. 0 <= persons[i] <= persons.length
  3. times is a strictly increasing array with all elements in [0, 10^9].
  4. TopVotedCandidate.q is called at most 10000 times per test case.
  5. TopVotedCandidate.q(int t) is always called with t >= times[0].

在选举中,第 i 张票是在时间为 times[i] 时投给 persons[i] 的。

现在,我们想要实现下面的查询函数: TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下,最近获得投票的候选人将会获胜。

示例:

输入:["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
输出:[null,0,1,1,0,0,1]
解释:
时间为 3,票数分布情况是 [0],编号为 0 的候选人领先。
时间为 12,票数分布情况是 [0,1,1],编号为 1 的候选人领先。
时间为 25,票数分布情况是 [0,1,1,0,0,1],编号为 1 的候选人领先(因为最近的投票结果是平局)。
在时间 15、24 和 8 处继续执行 3 个查询。 

提示:

  1. 1 <= persons.length = times.length <= 5000
  2. 0 <= persons[i] <= persons.length
  3. times 是严格递增的数组,所有元素都在 [0, 10^9] 范围中。
  4. 每个测试用例最多调用 10000 次 TopVotedCandidate.q
  5. TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]

Runtime: 1524 ms
Memory Usage: 21.9 MB
 1 class TopVotedCandidate {
 2     var m:[Int:Int] = [Int:Int]()
 3     var time:[Int]
 4 
 5     init(_ persons: [Int], _ times: [Int]) {
 6         self.time = times
 7         var n:Int = persons.count
 8         var lead:Int = -1
 9         var count:[Int:Int] = [Int:Int]()
10         for i in 0..<n
11         {
12             count[persons[i],default:0] += 1
13             if i == 0 || count[persons[i],default:0] >= count[lead,default:0]
14             {
15                 lead = persons[i]
16             }
17             m[times[i]] = lead
18         }        
19     }
20     
21     func q(_ t: Int) -> Int {
22         var i:Int = binarySearch(t)
23         return i < 0 ? m[time[-i-2],default:0] : m[time[i],default:0]      
24     }
25 
26     func binarySearch(_ target:Int) -> Int
27     {
28         var low = 0
29         var high = time.count - 1
30         var mid = (low + high) >> 1
31         
32         while low <= high {
33             let val = time[mid]
34             if target == val {
35                 return mid
36             } else if target < val {
37                 high = mid - 1
38             } else {
39                 low = mid + 1 
40             }
41             mid = (low + high) >> 1
42         }
43         return high
44     }
45 }
46 
47 /**
48  * Your TopVotedCandidate object will be instantiated and called as such:
49  * let obj = TopVotedCandidate(persons, times)
50  * let ret_1: Int = obj.q(t)
51  */

1672ms

 1 class TopVotedCandidate {
 2     var history: [Int]
 3     let times: [Int]
 4     init(_ persons: [Int], _ times: [Int]) {
 5         self.history = Array(repeating: 0, count: times.count)
 6         self.times = times
 7         var votes = Array(repeating: 0, count: persons.count + 1)
 8         var last = 0
 9         for i in 0..<persons.count {
10             let p = persons[i]
11             votes[p] += 1
12             if votes[p] >= votes[last] { last = p }
13             history[i] = last
14         }
15         print(history)
16         print(times)
17     }
18     
19     // return the biggest index of a time <= t
20     func binarySearch(_ t: Int) -> Int {
21         var i = 0, j = times.count
22         while i < j {
23             let m = (i + j) / 2
24             let a = times[m]
25             if a == t { return m }
26             if a > t { j = m }
27             else {
28                 if i == m { return m }
29                 i = m
30             }
31         }
32         return j
33     }
34     
35     func q(_ t: Int) -> Int {
36         let i = binarySearch(t)
37         return history[i]
38     }
39 }

1716ms

 1 class TopVotedCandidate {
 2     var rankings = [(Int, Int)]()
 3     
 4     init(_ persons: [Int], _ times: [Int]) {
 5         var map = [Int: Int]()
 6         var leader = -1
 7         var leaderCount = -1
 8         for i in 0..<persons.count {
 9             let sum = (map[persons[i]] ?? 0) + 1
10             map[persons[i]] = sum
11             if sum >= leaderCount {
12                 leader = persons[i]
13                 leaderCount = sum
14             }
15             rankings.append((times[i], leader))
16         }
17     }
18     
19     func q(_ t: Int) -> Int {
20         guard t < rankings.last!.0 else {
21             return rankings.last!.1
22         }
23         var left = 0
24         var right = rankings.count
25         while left < right {
26             let mid = left + (right - left) / 2
27             if rankings[mid].0 <= t {
28                 left = mid + 1
29             } else {
30                 right = mid
31             }
32         }
33         return rankings[left - 1].1
34     }
35 }

1732ms

 1 class TopVotedCandidate {
 2     var curMax = 0,  maxes = [Int](), votes = [Int: Int](), times = [Int]()
 3     // 0,1,1,0,0,1,0
 4     // 0 1 1 0 0 1 0
 5     init(_ persons: [Int], _ times: [Int]) {
 6         maxes = [Int](repeating: -1, count: persons.count)
 7         for (idx, person) in persons.enumerated() {
 8             votes[person] = (votes[person] ?? 0) + 1
 9             if let vote = votes[person], vote >= curMax {
10                 curMax = vote
11                 maxes[idx] = person
12             } else {
13                 maxes[idx] = maxes[idx - 1]
14             }
15         }
16         self.times = times
17     }
18     
19     func q(_ t: Int) -> Int {
20         var l = 0, r = times.count, idx = -1
21         while l < r {
22             var mid = (l + r) / 2
23             if times[mid] == t {
24                 idx = mid
25                 break
26             } else if times[mid] < t {
27                 l = mid + 1
28             } else {
29                 r = mid
30             }
31         }
32         if idx == -1 {
33             idx = l >= times.count ? l - 1 : times[l] > t ? l - 1 : l
34         }
35         return maxes[idx]
36     }
37 }

1756ms

 1 class TopVotedCandidate {
 2     var dict: [Int: Int]
 3     let times: [Int]
 4     init(_ persons: [Int], _ times: [Int]) {
 5         self.times = times
 6         var m = -1
 7         var leading = -1
 8         var d = [Int: Int]()
 9         dict = [Int: Int]()
10         for (i ,t) in times.enumerated() {
11             d[persons[i], default: 0] += 1
12             if let value = d[persons[i]], value >= m {
13                 m = value
14                 leading = persons[i]
15                 dict[t] = persons[i]
16             } else {
17                 dict[t] = leading
18             }
19         }
20     }
21     
22     func q(_ t: Int) -> Int {
23         var low = 0
24         var high = times.count-1
25         while low <= high {
26             let middle = (low + high) / 2
27             if times[middle] == t {
28                 return dict[times[middle]]!
29             } else if times[middle] > t {
30                 high = middle - 1
31             } else {
32                 low = middle + 1
33             }
34         }
35         return dict[times[low-1]]!
36     }
37 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift语言学习(三)基础操作符发布时间:2022-07-14
下一篇:
swift中的宏发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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