Insert an element into an array sorted according to frequency, then sort the array by frequency again

0 votes
asked Sep 11, 2017 by faizai-kiram

So I was asked asked to write an O(n) function, insertRanked(int[] list, int item), to insert an element into an array sorted by frequency (I have written a boolean function to check if int[] list is sorted by frequency). After inserting the element into the array, the array is then sorted again by frequency.

For example, insertRanked([65, 65, 65, 65, 1, 1, 1, 8, 8, 987, 987, 2, 2, 40], 2) should produce [65, 65, 65, 65, 1, 1, 1, 2, 2, 2, 8, 8, 987, 987, 40].

Is this possible to do in O(n)? I have thought of storing the elements and their counts into a LinkedHashMap and using Collections.sort() but the time complexity of Collections.sort() is O(n*log(n)).

1 Answer

0 votes
answered Sep 11, 2017 by nlp-java

Here's one approach to start you off could be based on count.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.TreeMap;

    public class SortCount {
        public static void main(String[] args) {
            int nums[] = {([65, 65, 65, 65, 1, 1, 1, 8, 8, 987, 987, 2, 2, 40};
            HashMap<Integer,Integer> counts = new HashMap<Integer,Integer>();

            for(int i = 0; i < nums.length; i++) {
                if(counts.containsKey(nums[
                    Integer c = counts.get(nums[i]) + 1;
                    counts.put(nums[i], c);
                }
                else {
                    counts.put(nums[i],1);
                }
            }

            ValueComparator<Integer,Integer> bvc = new ValueComparator<Integer,Integer>(counts);
            TreeMap<Integer,Integer> sortedMap = new TreeMap<Integer,Integer>(bvc);
            sortedMap.putAll(counts);

            ArrayList<Integer> output = new ArrayList<Integer>();
            for(Integer i : sortedMap.keySet()) {
                for(int c = 0; c < sortedMap.get(i); c++) {
                    output.add(i);
                }
            }

            System.out.println(output.toString());
        }
    }

//Which uses a Comparator class to compare the values in a Map:



 import java.util.Comparator;
    import java.util.Map;

    public class ValueComparator<T1,T2 extends Comparable<T2>> implements Comparator<T1> {
        Map<T1,T2> base;
        public ValueComparator(Map<T1,T2> base) {
            this.base = base;
        }

        @Override
        public int compare(T1 k1, T1 k2) {
            T2 val1 = base.get(k1);
            T2 val2 = base.get(k2);

            return val1.compareTo(val2);
        }
    }
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...