Given an array arr[] of size N representing integers required to be read as a data stream, the task is to calculate and print the median after reading every integer.
Examples:
Input: arr[] = { 5, 10, 15 } Output: 5 7.5 10 Explanation: After reading arr[0] from the data stream, the median is 5. After reading arr[1] from the data stream, the median is 7.5. After reading arr[2] from the data stream, the median is 10.
Input: arr[] = { 1, 2, 3, 4 } Output: 1 1.5 2 2.5
Approach: The problem can be solved using Ordered Set. Follow the steps below to solve the problem:
- Initialize a multi Ordered Set say, mst to store the array elements in a sorted order.
- Traverse the array using variable i. For every ith element insert arr[i] into mst and check if the variable i is even or not. If found to be true then print the median using (*mst.find_by_order(i / 2)).
- Otherwise, print the median by taking the average of (*mst.find_by_order(i / 2)) and (*mst.find_by_order((i + 1) / 2)).
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std;typedef tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> idxmst;// Function to find the median// of running integersvoid findMedian(int arr[], int N){ // Initialise a multi ordered set // to store the array elements // in sorted order idxmst mst; // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into mst mst.insert(arr[i]); // If i is an odd number if (i % 2 != 0) { // Stores the first middle // element of mst double res = *mst.find_by_order(i / 2); // Stores the second middle // element of mst double res1 = *mst.find_by_order( (i + 1) / 2); cout<< (res + res1) / 2.0<<" "; } else { // Stores middle element of mst double res = *mst.find_by_order(i / 2); // Print median cout << res << " "; } }}// Driver Codeint main(){ // Given stream of integers int arr[] = { 1, 2, 3, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call findMedian(arr, N);} |
Python3
# Python program to implement the approach for finding the median of running integers# Import the necessary module for Ordered Dictfrom collections import OrderedDictdef find_median(arr): # Initialize an ordered dictionary to store the elements in sorted order ordered_dict = OrderedDict() # Traverse the array for i in range(len(arr)): # Insert arr[i] into ordered_dict ordered_dict[arr[i]] = ordered_dict.get(arr[i], 0) + 1 # If i is an odd number if i % 2 != 0: # Find the middle elements and store them in a list mid = list(ordered_dict.keys())[i//2:i//2 + 2] # Calculate the median by taking the average of the middle elements median = (mid[0] + mid[1]) / 2 # Print median print("%.1f" % median, end=" ") else: # Find the middle element mid = list(ordered_dict.keys())[i//2] # Print median print(mid, end=" ")# Given stream of integersarr = [1, 2, 3, 3, 4]# Function callfind_median(arr)# This code is contributed by Shivam Tiwari |
Javascript
// JavaScript program to implement the approach for finding the median of running integers// Initialize an object to store the elements in sorted orderlet orderedObj = {};function find_median(arr) { // Traverse the array for (let i = 0; i < arr.length; i++) { // Insert arr[i] into orderedObj orderedObj[arr[i]] = (orderedObj[arr[i]] || 0) + 1; // If i is an odd number if (i % 2 !== 0) { // Find the middle elements and store them in a list let mid = Object.keys(orderedObj).slice(i / 2, i / 2 + 2); // Calculate the median by taking the average of the middle elements let median = (parseInt(mid[0]) + parseInt(mid[1])) / 2; // Print median process.stdout.write(median.toFixed(1) + " "); } else { // Find the middle element let mid = Object.keys(orderedObj)[i / 2]; // Print median process.stdout.write(mid + " "); } }}// Given stream of integerslet arr = [1, 2, 3, 3, 4];// Function callfind_median(arr);// This code is contributed by sdeadityasharma |
Java
import java.util.*;public class GFG { // Function to find the median // of running integers public static void findMedian(int[] arr) { // Initialize an ordered dictionary to store the elements in sorted order Map<Integer, Integer> ordered_dict = new TreeMap<>(); // Traverse the array for (int i = 0; i < arr.length; i++) { // Insert arr[i] into ordered_dict ordered_dict.put(arr[i], ordered_dict.getOrDefault(arr[i], 0) + 1); // If i is an odd number if (i % 2 != 0) { // Find the middle elements and store them in a list List<Integer> mid = new ArrayList<>(ordered_dict.keySet()).subList(i / 2, i / 2 + 2); // Calculate the median by taking the average of the middle elements double median = (mid.get(0) + mid.get(1)) / 2.0; // Print median System.out.print(String.format("%.1f", median) + " "); } else { // Find the middle element int mid = new ArrayList<>(ordered_dict.keySet()).get(i / 2); // Print median System.out.print(mid + " "); } } } // Driver Code public static void main(String[] args) { // Given stream of integers int[] arr = {1, 2, 3, 3, 4}; // Function call findMedian(arr); }}// This code is contributed By Shivam Tiwari |
C#
//C# program to implement the approach for finding the median of running integersusing System;using System.Collections.Generic;using System.Linq;class Program{ static void Main(string[] args) { // Given stream of integers int[] arr = { 1, 2, 3, 3, 4 }; // Function call find_median(arr); } // Function to find the median of running integers static void find_median(int[] arr) { // Initialize an ordered dictionary to store the elements in sorted order Dictionary<int, int> ordered_dict = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < arr.Length; i++) { // Insert arr[i] into ordered_dict if (ordered_dict.ContainsKey(arr[i])) { ordered_dict[arr[i]]++; } else { ordered_dict[arr[i]] = 1; } // If i is an odd number if (i % 2 != 0) { // Find the middle elements and store them in a list var mid = ordered_dict.Keys.ToList().GetRange(i / 2, 2); // Calculate the median by taking the average of the middle elements var median = (mid[0] + mid[1]) / 2.0; // Print median Console.Write("{0:F1} ", median); } else { // Find the middle element var mid = ordered_dict.Keys.ToList().GetRange(i / 2, 1); // Print median Console.Write("{0} ", mid[0]); } } }}// This code is contributed by shivamsharma215 |
Output
1 1.5 2 2.5 3
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!