题目

https://leetcode.com/problems/online-election/

题解

我的解法是，用预计算（加强堆，O(nlogn)） + 二分查找（用的自带TreeMap，查找复杂度O(logn)）。

实际上，最优解可以达到预计算 O(n)，只需要比较当前新元素的 count 与当前最大元素的 count，并更新最大元素即可。

下面来说一下为什么用加强堆。

系统自带的堆，它不能动态修改元素。
就是说，已经入堆的元素，如果参与排序的指标方法变化，它不能自动调整。所以有了加强堆。
对于已经入堆的元素，它的字段发生改变的时候，能够以O(logN)的复杂度调整整个堆。

class TopVotedCandidate {
    TreeSet<Info> treeSet;

    public TopVotedCandidate(int[] persons, int[] times) {
        HeapGreater<Person> heap = new HeapGreater<>((o1, o2) -> {
            if (o1.count != o2.count) {
                return o2.count - o1.count;
            } else {
                return o2.updatedTime - o1.updatedTime;
            }
        });
        HashMap<Integer, Person> map = new HashMap<>(); // index, person
        treeSet = new TreeSet<>((o1, o2) -> o1.time - o2.time);
        for (int i = 0; i < persons.length; i++) {
            if (!map.containsKey(persons[i])) {
                Person p = new Person(1, persons[i], times[i]);
                map.put(persons[i], p);
                heap.push(p);
            } else {
                Person p = map.get(persons[i]);
                p.count++;
                p.updatedTime = times[i];
                heap.resign(p);
            }
            treeSet.add(new Info(heap.peek().index, times[i]));
        }
    }

    public int q(int t) {
        return treeSet.floor(new Info(-1, t)).index;
    }
}

class Info {
    int index;
    int time;

    public Info(int index, int time) {
        this.index = index;
        this.time = time;
    }
}

class Person {
    int count;
    int index;
    int updatedTime;

    public Person(int count, int index, int updatedTime) {
        this.count = count;
        this.index = index;
        this.updatedTime = updatedTime;
    }
}

/* * T一定要是非基础类型，有基础类型需求包一层 */
class HeapGreater<T> {
    private ArrayList<T> heap;
    private HashMap<T, Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    public T peek() {
        return heap.get(0);
    }

    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    private void heapInsert(int index) {
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if (best == index) {
                break;
            }
            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o2, i);
        indexMap.put(o1, j);
    }
}