缓存、随机访问与流式索引

import heapq


class MedianFinder:
    """Running median of a stream of numbers (LC 295)."""

    def __init__(self):
        self.low: list[int] = []  # the smaller half, negated so heapq gives a max-heap
        self.high: list[int] = []  # the larger half, a min-heap

    def add(self, x: int) -> None:
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))  # the largest of low moves up
        if len(self.high) > len(self.low):  # low keeps the same size or one more
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

// Running median of a stream of numbers (LC 295).
class MedianFinder {
    priority_queue<int> low;  // the smaller half, largest on top
    priority_queue<int, vector<int>, greater<int>> high;  // the larger half, smallest on top

public:
    void add(int x) {
        low.push(x);
        high.push(low.top());  // the largest of low moves up
        low.pop();
        if (high.size() > low.size()) {  // low keeps the same size or one more
            low.push(high.top());
            high.pop();
        }
    }
    double median() const {
        return low.size() > high.size() ? low.top() : ((double)low.top() + high.top()) / 2;
    }
};

// Running median of a stream of numbers (LC 295).
class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder()); // the smaller half
    private final PriorityQueue<Integer> high = new PriorityQueue<>(); // the larger half

    void add(int x) {
        low.offer(x);
        high.offer(low.poll()); // the largest of low moves up
        if (high.size() > low.size()) low.offer(high.poll()); // low keeps the same size or one more
    }

    double median() {
        return low.size() > high.size() ? low.peek() : ((double) low.peek() + high.peek()) / 2;
    }
}

import "container/heap"

// intHeap is a container/heap of ints in the order less gives.
type intHeap struct {
	xs   []int
	less func(a, b int) bool
}

func (h *intHeap) Len() int           { return len(h.xs) }
func (h *intHeap) Less(i, j int) bool { return h.less(h.xs[i], h.xs[j]) }
func (h *intHeap) Swap(i, j int)      { h.xs[i], h.xs[j] = h.xs[j], h.xs[i] }
func (h *intHeap) Push(x any)         { h.xs = append(h.xs, x.(int)) }
func (h *intHeap) Pop() any {
	x := h.xs[len(h.xs)-1]
	h.xs = h.xs[:len(h.xs)-1]
	return x
}

// MedianFinder keeps the running median of a stream of numbers (LC 295).
type MedianFinder struct {
	low, high *intHeap
}

func NewMedianFinder() *MedianFinder {
	return &MedianFinder{
		low:  &intHeap{less: func(a, b int) bool { return a > b }}, // the smaller half, largest on top
		high: &intHeap{less: func(a, b int) bool { return a < b }}, // the larger half, smallest on top
	}
}

func (m *MedianFinder) Add(x int) {
	heap.Push(m.low, x)
	heap.Push(m.high, heap.Pop(m.low)) // the largest of low moves up
	if m.high.Len() > m.low.Len() { // low keeps the same size or one more
		heap.Push(m.low, heap.Pop(m.high))
	}
}

func (m *MedianFinder) Median() float64 {
	if m.low.Len() > m.high.Len() {
		return float64(m.low.xs[0])
	}
	return float64(m.low.xs[0]+m.high.xs[0]) / 2
}

import random


class RandomizedSet:
    """insert, remove and get_random in O(1) on average (LC 380)."""

    def __init__(self):
        self.items: list[int] = []  # the values, in no particular order
        self.where: dict[int, int] = {}  # value -> its index in items

    def insert(self, x: int) -> bool:
        if x in self.where:
            return False
        self.where[x] = len(self.items)
        self.items.append(x)
        return True

    def remove(self, x: int) -> bool:
        if x not in self.where:
            return False
        i, last = self.where.pop(x), self.items.pop()
        if i < len(self.items):  # x was not last: the last value fills its slot
            self.items[i] = last
            self.where[last] = i
        return True

    def get_random(self) -> int:
        return random.choice(self.items)

// insert, remove and getRandom in O(1) on average (LC 380).
class RandomizedSet {
    vector<int> items;  // the values, in no particular order
    unordered_map<int, int> where;  // value -> its index in items

public:
    bool insert(int x) {
        if (where.count(x)) return false;
        where[x] = items.size();
        items.push_back(x);
        return true;
    }
    bool remove(int x) {
        auto it = where.find(x);
        if (it == where.end()) return false;
        int i = it->second, last = items.back();
        items[i] = last;  // the last value fills x's slot (x itself if it was last)
        where[last] = i;
        items.pop_back();
        where.erase(x);
        return true;
    }
    int getRandom() const { return items[rand() % items.size()]; }
};

// insert, remove and getRandom in O(1) on average (LC 380).
class RandomizedSet {
    private final List<Integer> items = new ArrayList<>(); // the values, in no particular order
    private final Map<Integer, Integer> where = new HashMap<>(); // value -> its index in items
    private final Random random = new Random();

    boolean insert(int x) {
        if (where.containsKey(x)) return false;
        where.put(x, items.size());
        items.add(x);
        return true;
    }

    boolean remove(int x) {
        Integer i = where.get(x);
        if (i == null) return false;
        int last = items.get(items.size() - 1);
        items.set(i, last); // the last value fills x's slot (x itself if it was last)
        where.put(last, i);
        items.remove(items.size() - 1);
        where.remove(x);
        return true;
    }

    int getRandom() {
        return items.get(random.nextInt(items.size()));
    }
}

import "math/rand"

// RandomizedSet supports Insert, Remove and GetRandom in O(1) on average (LC 380).
type RandomizedSet struct {
	items []int       // the values, in no particular order
	where map[int]int // value -> its index in items
}

func NewRandomizedSet() *RandomizedSet { return &RandomizedSet{where: map[int]int{}} }

func (s *RandomizedSet) Insert(x int) bool {
	if _, ok := s.where[x]; ok {
		return false
	}
	s.where[x] = len(s.items)
	s.items = append(s.items, x)
	return true
}

func (s *RandomizedSet) Remove(x int) bool {
	i, ok := s.where[x]
	if !ok {
		return false
	}
	last := s.items[len(s.items)-1]
	s.items[i] = last // the last value fills x's slot (x itself if it was last)
	s.where[last] = i
	s.items = s.items[:len(s.items)-1]
	delete(s.where, x)
	return true
}

func (s *RandomizedSet) GetRandom() int { return s.items[rand.Intn(len(s.items))] }