algorithm - sort most repeated number first (descending order)-CodePudding

I have a list of numbers, for example:

first line means the number 10 repeats 4 times, the second line means the number 5 repeats thrice and so on. The objective is to sort these numbers, the most repeated first in descending order. I think using Hashmap to record the data and then feeding it to treeset and sort by value would be the most efficient way -> O(n log n), but is there a more efficient way? I've heard this problem is solved with max-heap, but I dont think heap can do better than O(n log n).

CodePudding user response：

Assuming the number is unique,

Why sort? just loop through every key save max occurence, and you’ll get it in O(n)

maxNum = 0
maxValue = -1
loop numbers:
   if (numbers[i].value > maxValue) :
     maxValue = numbers[i].value
     maxNum = numbers[i].key
return maxNum;

CodePudding user response：

I'm assuming you have the values and weights paired. (The weight is the number of times a value occurs.) And the pairs are in some sort of list or array.

static void sortDemo () {
    Integer [][] nums = { {5,3}, {7,1}, {10, 4}, {-2, 2} };
    Arrays.sort (nums, 
            (Integer [] a, Integer [] b) -> (b[1].compareTo (a[1])));   
    System.out.println (Arrays.deepToString(nums));
}

Arrays is a Java class with static methods useful for on arrays. Some of the methods sort the array. If you have a List or otherCollection, you can find methods to sort those.

The sort methods you are interested in allow you to code your own Comparator.