-
Notifications
You must be signed in to change notification settings - Fork 0
/
274.swift
40 lines (32 loc) · 1.18 KB
/
274.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// passed
class Solution1 { // O(n*log(n))
func hIndex(_ citations: [Int]) -> Int {
// 最直接的思路:排序后依次检查 c[i] >= i+1
if citations.isEmpty { return 0 }
for (i, c) in citations.sorted(by: >).enumerated() {
if c < i + 1 { return i }
}
return citations.count
}
}
class Solution { // O(n)
func hIndex(_ citations: [Int]) -> Int {
// 空间换时间,桶排?
// 使用桶存储每个数字出现了多少次,超过最大的放到最大的里面
// 为了方便,从0开始统计,使用多一格的桶
if citations.isEmpty { return 0 }
var bracket = Array(repeating: 0, count: citations.count + 1)
for c in citations {
let c = min(c, citations.count)
bracket[c] += 1
}
for i in (0..<bracket.count-1).reversed() { // accumulate
bracket[i] += bracket[i+1]
}
for (i, c) in bracket.reversed().enumerated() { // i is not reversed!!
let i = bracket.count - 1 - i // so we reverse it
if c >= i { return i }
}
fatalError()
}
}