LeetCode 571: Find Median Given Frequency of Numbers

Explanation:

The problem asks us to find the median of a list of numbers given the frequency of each number. The frequency of a number represents how many times that number appears in the list. We need to return the median of the numbers in the list.

To solve this problem, we can follow these steps:

1. Create a list to store the numbers based on their frequency.
2. Iterate through the list of numbers and their frequencies, adding each number to the list the corresponding number of times.
3. Sort the list of numbers.
4. Calculate the median based on the size of the list:
   • If the list has an odd number of elements, the median is the middle element.
   • If the list has an even number of elements, the median is the average of the middle two elements.

The time complexity of this approach is O(NlogN) due to the sorting step, where N is the total number of elements in the list. The space complexity is O(N) to store the list of numbers based on their frequencies.

: :

import java.util.ArrayList;
import java.util.List;

class Solution {
    public double findMedian(int[] nums, int[] freq) {
        List<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < freq[i]; j++) {
                list.add(nums[i]);
            }
        }
        
        Collections.sort(list);
        
        int n = list.size();
        if (n % 2 == 0) {
            return (list.get(n/2 - 1) + list.get(n/2)) / 2.0;
        } else {
            return list.get(n/2);
        }
    }
}