911.在线选举.md

911.在线选举

/*
 * @lc app=leetcode.cn id=911 lang=typescript
 *
 * [911] 在线选举
 */

// @lc code=start
class TopVotedCandidate {
  constructor(persons: number[], times: number[]) {}

  q(t: number): number {}
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * var obj = new TopVotedCandidate(persons, times)
 * var param_1 = obj.q(t)
 */
// @lc code=end

解法 1: 二分查找

class TopVotedCandidate {
  private _persons: { time: number; person: number }[]
  constructor(persons: number[], times: number[]) {
    this._persons = []
    const cache: { [k: number]: number } = {}
    let max = persons[0]
    for (let i = 0; i < times.length; i++) {
      const person = persons[i]
      cache[person] = (cache[person] ?? 0) + 1
      if (cache[person] >= cache[max]) max = person

      this._persons[i] = { time: times[i], person: max }
    }
  }

  q(t: number): number {
    let [left, right] = [0, this._persons.length - 1]
    while (left < right) {
      const mid = (left + right + 1) >>> 1
      if (this._persons[mid].time > t) {
        right = mid - 1
      } else {
        left = mid
      }
    }

    return this._persons[right].person
  }
}

解法 2: 保存所有时间对应的候选人

class TopVotedCandidate {
  private _persons: number[]
  constructor(persons: number[], times: number[]) {
    this._persons = []
    const cache: { [k: number]: number } = {}
    let max = persons[0]

    for (let i = 0, j = 0; i <= times[times.length - 1]; i++) {
      if (times[j] === i) {
        const person = persons[j]
        cache[person] = (cache[person] ?? 0) + 1
        if (cache[person] >= cache[max]) max = person
        j++
      }

      this._persons[i] = max
    }
  }

  q(t: number): number {
    const persons = this._persons
    return t > persons.length - 1 ? persons[persons.length - 1] : persons[t]
  }
}

Case

test.each([
  {
    input: {
      ops: ['TopVotedCandidate', 'q', 'q', 'q', 'q', 'q', 'q'],
      param: [
        [
          [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],
  },
  {
    input: {
      ops: ['TopVotedCandidate', 'q', 'q', 'q', 'q', 'q', 'q', 'q', 'q', 'q', 'q'],
      param: [
        [
          [0, 0, 0, 0, 1],
          [0, 6, 39, 52, 75],
        ],
        [45],
        [49],
        [59],
        [68],
        [42],
        [37],
        [99],
        [26],
        [78],
        [43],
      ],
    },
    output: [null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  },
  {
    input: {
      ops: ['TopVotedCandidate', 'q', 'q', 'q', 'q', 'q', 'q'],
      param: [
        [
          [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],
  },
])('input: ops = $input.ops, param = $input.param', ({ input: { ops, param }, output }) => {
  const topVotedCandidate = new TopVotedCandidate(param[0][0] as number[], param[0][1] as number[])
  const res: (number | null)[] = [null]
  for (let i = 1; i < param.length; i++) {
    res.push(topVotedCandidate.q(param[i][0] as number))
  }
  expect(res).toEqual(output)
})