टीएल;डीआर
- समस्या: सीटीसीआई समस्या १७.२० का तकनीकी विवरण।
- दृष्टिकोण: सीटीसीआई problem १७.२०: track and maintain the median of a numerical data stream using a Max-Heap and Min-Heap.
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या १७.२० का एक स्पष्ट विवरण प्रदान करता है।
१. संदर्भ और समस्या कथन
सीटीसीआई problem १७.२०: track and maintain the median of a numerical data stream using a Max-Heap and Min-Heap.
२. कोड और कार्यान्वयन
public class ContinuousMedian {
private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Left lower half
private final PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Right upper half
public void insert(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.offer(num);
else minHeap.offer(num);
if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
else if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
}
public double getMedian() {
if (maxHeap.size() == minHeap.size()) return (maxHeap.peek() + minHeap.peek()) / 2.0;
return maxHeap.peek();
}
}
३. सारांश और एज केसेस
हमेशा सीमांत स्थितियों और इनपुट की जांच करें।