Given the list [x_1, x_2, ..., x_n]. I am looking for an effective implementation of a function that takes a list as input and displays a list of types [(x_1 ', n_1), ..., (x_m', n_m)], where x_i is everything and n_i is the number of occurrences x_i 'in the input list .
There is a trivial way to do this in quadratic time without mutation. However, a typical simple method in an imperative language, where x_i can be represented by small numerical values, is to use an array and the [x_i] ++ array for each list item, then scan the array for non-zero entries and use this to create an output list. Then the runtime is linear (with poor performance for very small inputs).
There's an obvious best implementation without mutation. If x_i has a well-defined order, you can build a binary search tree. Look up (x_i, k) in the tree. If it is not inserted in the tree (x_i, 1), otherwise delete (x_i, k) from the tree and insert (x_i, k + 1). Finally, navigate the tree that converts it to a list. Also, sort the list, and then swipe it along linear time. Both are O (nlog (n)).
Is there a better algorithm without mutation?
source
share