Skip to main content

Leetcode 295. Find Median from Data Stream. Python

 295Find Median from Data Stream


The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

 

Constraints:

  • -105 <= num <= 105
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 104 calls will be made to addNum and findMedian.


Solution :

 class MedianFinder:

    def __init__(self):
        self.s, self.l = [], []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.s, -1 * num)
        
        if self.s and self.l and (-1 * self.s[0]) > self.l[0] :
            n = -1 * heapq.heappop(self.s)
            heapq.heappush(self.l, n)
        
        if len(self.s) > len(self.l) + 1 :
            n = -1 * heapq.heappop(self.s)
            heapq.heappush(self.l, n)
        
        if len(self.l) > len(self.s) + 1 :
            n = heapq.heappop(self.l)
            heapq.heappush(self.s, -1 * n)
            
    def findMedian(self) -> float:
        if len(self.s) > len(self.l):
            return -1 * self.s[0]
        elif len(self.l) > len(self.s):
            return self.l[0]
        return (-1 * self.s[0] + self.l[0])/2

Explaination :




Comments

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Number of Connected Components in an Undirected Graph (Python)

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...

Leetcode 347. Top K Frequent Elements. Python (Bubble Sort)

Top K Frequent Elements Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: 1 <= nums.length <= 10 5 -10 4  <= nums[i] <= 10 4 k  is in the range  [1, the number of unique elements in the array] . It is  guaranteed  that the answer is  unique .   Follow up:  Your algorithm's time complexity must be better than  O(n log n) , where n is the array's size. Solution : class Solution:     def topKFrequent(self, n: List[int], k: int) -> List[int]:                  # [1,1,1,2,2,3] &  k = 2                  f = [[] for i in range(len(n) + 1)]         # f = [...