So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.
For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like...
histogramBinSizes = [5, 18, 11, 0, ...]
Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array percentileBinSizes
)
To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that histogramBinSizes
and percentileBinSizes
both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?
I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.