「算法」911. 在线选举

<p/><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/feeca81d7d5799d9.jpg" contenteditable="false" img-data="{"format":"jpeg","size":190512,"height":900,"width":1600}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><p>

</p><p>
</p><p>
</p><h1 id="rlb15">题解</h1><div class="image-package"><img src="https://img.haomeiwen.com/i1648392/a9264953f0d7b36d.jpg" contenteditable="false" img-data="{"format":"jpeg","size":68767,"height":802,"width":1344}" class="uploaded-img" style="min-height:200px;min-width:200px;" width="auto" height="auto"/>
</div><h2 id="xvfb7">Swift</h2><blockquote><p>class TopVotedCandidate {
// 预排序好的结果
var tops = Int

// 投票的结果
var voteCounts = Int: Int

// 传入的时间
var times: [Int]!

init(_ persons: [Int], _ times: [Int]) {
self.times = times

// 预插值
voteCounts[-1] = -1
var top = -1

for p in persons {
voteCounts[p, default: 0] += 1

if voteCounts[p]! >= voteCounts[top]! {
top = p
}

tops.append(top)
}
}

func q(_ t: Int) -> Int {
var left = 0, right = times.count - 1

while left < right {
let mid = left + (right - left + 1) / 2

if times[mid] <= t {
left = mid
} else {
right = mid - 1
}
}

return tops[left]
}
}

let obj = TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30])

print(obj.q(3))
print(obj.q(12))
print(obj.q(25))
print(obj.q(15))
print(obj.q(24))
print(obj.q(8))
</p></blockquote><p>
</p><h2 id="m0fct">Dart</h2><blockquote><p>class TopVotedCandidate {
// 预排序好的结果
var tops = <int>[];

// 投票的结果
var voteCounts = Map<int, int>();

// 传入的时间
late List<int> times;

TopVotedCandidate(List<int> persons, List<int> times) {
this.times = times;

// 预插值
voteCounts[-1] = -1;
int top = -1;

for (var p in persons) {
voteCounts[p] = (voteCounts[p] ?? 0) + 1;

if (voteCounts[p]! >= voteCounts[top]!) {
top = p;
}

tops.add(top);
}
}

int q(int t) {
var left = 0, right = times.length - 1;

while (left < right) {
var mid = (left + (right - left + 1) / 2).toInt();

if (times[mid] <= t) {
left = mid;
} else {
right = mid - 1;
}
}

return tops[left];
}
}

void main() {
var obj =
TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);

print(obj.q(3));
print(obj.q(12));
print(obj.q(25));
print(obj.q(15));
print(obj.q(24));
print(obj.q(8));
}
</p></blockquote><p>
</p><p>
</p>