[Swift]LeetCode1157.子数组中占绝大多数的元素|OnlineMajorityElementInSubarray ...

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

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

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

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

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

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

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

实现一个 MajorityChecker 的类，它应该具有下述几个 API：

MajorityChecker(int[] arr) 会用给定的数组 arr 来构造一个 MajorityChecker 的实例。
int query(int left, int right, int threshold) 有这么几个参数：
- 0 <= left <= right < arr.length 表示数组 arr 的子数组的长度。
- 2 * threshold > right - left + 1，也就是说阀值 threshold 始终比子序列长度的一半还要大。

每次查询 query(...) 会返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现阀值次数 threshold 的元素，如果不存在这样的元素，就返回 -1。

示例：

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

提示：

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
对于每次查询，0 <= left <= right < len(arr)
对于每次查询，2 * threshold > right - left + 1
查询次数最多为 10000

2304ms

 1 class MajorityChecker {
 2     var arr:[Int] = [Int]()
 3 
 4     init(_ arr: [Int]) {
 5         self.arr = arr        
 6     }
 7     
 8     func query(_ left: Int, _ right: Int, _ threshold: Int) -> Int {
 9         var count:[Int] = [Int](repeating:0,count:200000)
10         if left <= right
11         {
12             for i in left...right
13             {
14                 if ++count[arr[i] - 1] == threshold
15                 {
16                     return arr[i]
17                 }
18             }
19         }        
20         return -1
21     }
22 }
23 
24 /*扩展Int类，实现自增++、自减--运算符*/
25 extension Int{
26     //++前缀:先自增再执行表达示
27     static prefix func ++(num:inout Int) -> Int {
28         //输入输出参数num
29         num += 1
30         //返回加1后的数值
31         return num
32     }
33 }
34 
35 /**
36  * Your MajorityChecker object will be instantiated and called as such:
37  * let obj = MajorityChecker(arr)
38  * let ret_1: Int = obj.query(left, right, threshold)
39  */

 1 class MajorityChecker {
 2     var a:[Int] = [Int]()
 3     var big:[Int] = [Int]()
 4     var fs:[[Int]] = [[Int]]()
 5     var B:Int = 0
 6 
 7     init(_ arr: [Int]) {
 8         self.a = arr
 9         let n:Int = a.count
10         self.B = Int(sqrt(Double(n)))
11         var f:[Int] = [Int](repeating:0,count:20001)
12         for v in a
13         {
14             f[v] += 1
15         }
16         var bigger:[Int] = [Int](repeating:0,count:n)
17         var p:Int = 0
18         for i in 1...20000
19         {
20             if f[i] >= B
21             {                
22                 bigger[p] = i
23                 p += 1
24             }
25         }
26         big = bigger[0..<p] 
27         fs = [[Int]](repeating:[Int](repeating:0,count:n+1),count:p)
28         for i in 0..<p
29         {
30             for j in 0..<n
31             {
32                 if a[j] == big[i]
33                 {
34                     fs[i][j+1] = fs[i][j] + 1
35                 }
36                 else
37                 {
38                     fs[i][j+1] = fs[i][j]
39                 }
40             }
41         }
42     }
43     
44     func query(_ left: Int, _ right: Int, _ threshold: Int) -> Int {
45         if right - left + 1 <= 2*B
46         {
47             var best:Int = -1
48             var f:Int = 0
49             for i in  left...right
50             {
51                 if best == a[i]
52                 {
53                     f += 1
54 
55                 }
56                 else if f == 0
57                 {
58                     best = a[i]
59                 }
60                 else
61                 {
62                     f -= 1
63                 }
64             }
65             var ct:Int = 0
66             for i in  left...right
67             {
68                 if a[i] == best
69                 {
70                     ct += 1
71                 }
72             }
73             return ct >= threshold ? best : -1
74         }
75         else
76         {
77             for i in 0..<big.count
78             {
79                 var ff:Int = fs[i][right+1] - fs[i][left]
80                 if ff >= threshold
81                 {
82                     return big[i]
83                 }                
84             }
85             return -1
86         }
87     }
88 }
89 
90 /**
91  * Your MajorityChecker object will be instantiated and called as such:
92  * let obj = MajorityChecker(arr)
93  * let ret_1: Int = obj.query(left, right, threshold)
94  */