Design a Number Container System
MediumHash TableDesignHeap (Priority Queue)Ordered Set
Solution
container는 현재index의num을 저장heaps는 현재num을 가지고 있는index를Heap을 저장Heap을 통해, 현재num을 가지고 있는 가장 작은 인덱스를 검색change를 할 때 마다, 해당Heap을 정리하지 않고,find를 할 때, 현재container에서index가num을 가지고 있는지를 통해 정리
change
container에 주어진index에num을 반영- 이전에
index가 다른num을 가지고 있는 경우, 해당num의Heap의 가장 작은 인덱스가 주어진index라면, 해당index삭제
find
heaps를 통해, 주어진num을 가지고 있는index들을 저장하고 있는Heap을 검색Heap이 없는 경우,-1을 반환Heap을 순환하면서,container의index가 가지고 있는num과 일치하는 경우, 해당index를 반환- 일치하지 않는 경우는,
Heap에서 삭제
import { Heap } from '@algorithm/lib';
export class NumberContainers {
private readonly container: Map<number, number>;
private readonly heaps: Map<number, Heap<number>>;
constructor() {
this.container = new Map();
this.heaps = new Map();
}
private getHeap(num: number): Heap<number> {
const heap = this.heaps.get(num);
if (heap !== undefined) {
return heap;
}
const newHeap = new Heap<number>((a, b) => a - b);
this.heaps.set(num, newHeap);
return newHeap;
}
change(index: number, num: number): void {
const prevNum = this.container.get(index);
if (prevNum !== undefined && this.heaps.has(prevNum)) {
const prevHeap = this.getHeap(prevNum);
if (prevHeap.peek === index) {
prevHeap.pop();
}
}
const pq = this.getHeap(num);
pq.push(index);
this.container.set(index, num);
}
find(num: number) {
if (!this.heaps.has(num)) {
return -1;
}
const heap = this.getHeap(num);
while (!heap.isEmpty) {
if (heap.peek !== undefined && this.container.get(heap.peek) === num) {
return heap.peek;
}
heap.pop();
}
return -1;
}
}Complexity
- Time:
- Space: