LeetCode 911. Online Election

题目

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: ["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]]  
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 <= persons.length = times.length <= 5000  
0 <= persons[i] <= persons.length  
times is a strictly increasing array with all elements in [0, 10^9].  
TopVotedCandidate.q is called at most 10000 times per test case.  
TopVotedCandidate.q(int t) is always called with t >= times[0].  

思路

题目其实挺简单,主要是理解题目的意思. 用一个数组存放每个时间点的winner, 然后再用二分法找出时间点的lower bound即可, 容易错的是一些boundary check

Swift 题解

class TopVotedCandidate {

    var result: [Int]
    var times: [Int]

    init(_ persons: [Int], _ times: [Int]) {
        self.result = Array(repeating: -1, count: times.count)
        var count = [Int: Int]()
        var max = -1
        for (index, person) in persons.enumerated() {
            if let currentCount = count[person] {
                count[person] = (currentCount + 1)
            } else {
                count[person] = 1
            }

            if count[person]! >= max {
                max = count[person]!
                result[index] = person
            } else {
                result[index] = result[index - 1]
            }
        }

        self.times = times
    }

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

        while left <= right {
            let middle = (left + right) / 2
            let time = times[middle]
            if time == t {
                return result[middle]
            } else if time > t {
                right = middle - 1
                if right > 0 {
                    if times[right] < t {
                        return result[right]
                    }
                }
            } else {
                left = middle + 1
                if left < times.count {
                    if times[left] > t {
                        return result[middle]
                    }
                }
            }
        }

        return left == times.count ? result.last! : -1
    }
}

chenbo

编程爱好者

Singapore