Leetcode刷题java之295. 数据流的中位数（一天一道编程题之四十九天）

布满荆棘的人生 2023-07-22 09:25 17阅读 0赞

执行结果：

通过

显示详情

执行用时 :959 ms, 在所有 Java 提交中击败了7.11% 的用户

内存消耗 :49.6 MB, 在所有 Java 提交中击败了100.00%的用户

题目：

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。  
double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)  
addNum(2)  
findMedian() -> 1.5  
addNum(3)  
findMedian() -> 2

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-median-from-data-stream  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

加入的时候直接加入到集合的相对位置，相当于插入排序了

获取的时候就获取中间索引就好了

代码：

class MedianFinder {
        public ArrayList<Integer> list;
        /** initialize your data structure here. */
        public MedianFinder() {
            list=new ArrayList<>();
        }
        
        public void addNum(int num) {
            if(list.size()==0)
            {
                list.add(num);
                return;
            }
            int index=0;
            for(int x:list)
            {
                if(num<x)
                {
                    list.add(index,num);
                    return;
                }
                index++;
            }
            if(index==list.size())
            {
                list.add(num);
            }
        }
        
        public double findMedian() {
            int size=list.size();
            if(size==0)
            {
                return 0.0;
            }
            if(size%2==0)
            {
                return (list.get(size/2)+list.get(size/2-1))/2.0;
            }else
            {
                return list.get(size/2)/1.0;
            }
        }
    }
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */