LeetCode（算法）- 295. 数据流的中位数

LeetCode（算法）- 295. 数据流的中位数

题目大意：略

解题思路

相关企业

字节跳动亚马逊（Amazon）微软（Microsoft）Facebook苹果（Apple）谷歌（Google）Indeed领英（LinkedIn）优步（Uber）英伟达（NVIDIA）

AC 代码

Java

// 解决方案(1)class MedianFinder { int[] data; int len; /** initialize your data structure here. */ public MedianFinder() { data = new int[100000]; len = 0; } public void addNum(int num) { if (len == 0) { data[len++] = num; return; } int idx = search(num); len++; for (int i = len - 1; i > idx; i--) { data[i] = data[i - 1]; } data[idx] = num; } public double findMedian() { if (len % 2 == 0) { return (data[len / 2 - 1] + data[len / 2]) / 2.0; } else { return data[len / 2]; } } private int search(int val) { int l = 0, r = len - 1; while (l <= r) { int mid = (l + r) / 2; if (data[mid] == val) { return mid; } else if (data[mid] < val) { l = mid + 1; if (l > r) { return l; } } else { r = mid - 1; if (r < l) { return r + 1; // 当 l == r 时, 此时这个场景应该取 r + 1 自己举个例子就知道了 } } } return -1; }} // 解决方案(2)class MedianFinder { Queue A, B; public MedianFinder() { A = new PriorityQueue<>(); // 小顶堆，保存较大的一半 B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半 } public void addNum(int num) { if(A.size() != B.size()) { A.add(num); B.add(A.poll()); } else { B.add(num); A.add(B.poll()); } } public double findMedian() { return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0; }}

C++

class MedianFinder {public: priority_queue, greater> A; // 小顶堆，保存较大的一半 priority_queue, less> B; // 大顶堆，保存较小的一半 MedianFinder() { } void addNum(int num) { if(A.size() != B.size()) { A.push(num); B.push(A-()); A.pop(); } else { B.push(num); A.push(B-()); B.pop(); } } double findMedian() { return A.size() != B.size() ? A-() : (A-() + B-()) / 2.0; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。