How to print amount of occurrences of specific string in descending order?-CodePudding

I'm looking to use a String[] of logs detailing users who have connected to a website to print out in descending order the amount of times each user has connected. Each log contains some information but the unique userID is always within the first index of the array.

I'm trying to go through the array in O(N) time, calculate how many times each user has connected by adding them to a HashMap, then print out the connected users in descending order based on how many times they have connected. How can this be done? I'm open to switching up my entire implementation if there is an easier way to track the amount of occurrences within the String[]. I have attached an example below:

 // Connection logs in the form [Username, Location, time]
String[] logs = {
    "name1,Chicago,8pm",
    "name2,New York,6pm",
    "name3,Los Angeles,2am",
    "name1,Chicago,3pm",
    "name1,Chicago,12pm",
    "name4,Miami,3pm"
    "name4,Miami,6pm"
};

printConnections(logs);

/* Desired output:
    name1: 3
    name2: 2
    name4: 2
    name3: 1
*/

public static void printConnections(String[] connections){
    HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
    for (String log : connections){
        String name = log.split(",")[0];
        if (hashmap.containsKey(name)){
            hashmap.replace(name, hashmap.get(name)   1);
        }
        else{
            hashmap.put(name, 1);
        }
    }
    // Print all key/values in descending order of value
}

CodePudding user response：

TLDR:

// Print all key/values in descending order of value
var sorted = hashmap.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()));
sorted.forEach(pair->System.out.println(pair.getKey()   ": "   pair.getValue()));

Output:

name1: 3
name4: 2
name3: 1
name2: 1

How it works?

hashmap.entrySet() will return a set of Map.Entry objects .stream() will return a stream of these objects .sorted() will sort the stream by the value of the Map.Entry objects

Full:

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

public class Main {

    public static void printConnections(String[] connections) {
        HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
        for (String log : connections) {
            String name = log.split(",")[0];
            if (hashmap.containsKey(name)) {
                hashmap.replace(name, hashmap.get(name)   1);
            } else {
                hashmap.put(name, 1);
            }
        }
        // Print all key/values in descending order of value
        var sorted = hashmap.entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()));
        sorted.forEach(pair->System.out.println(pair.getKey()   ": "   pair.getValue()));
    }

    public static void main(String[] args) {

        // Connection logs in the form [Username, Location, time]
        String[] logs = {
                "name1,Chicago,8pm",
                "name2,New York,6pm",
                "name3,Los Angeles,2am",
                "name1,Chicago,3pm",
                "name1,Chicago,12pm",
                "name4,Miami,3pm",
                "name4,Miami,6pm"
        };

        printConnections(logs);
    }
}

CodePudding user response：

First of all, I'm assuming that by O(n) you mean O(n) where n = number of unique users (ie. hashmap.keySet().size()). Unfortunately, your problem involves sorting which is at best O(n*log(n)) complexity, so I don't think it is possible to do this in O(n) time. However, I have some code to still get the job done:

ArrayList<Entry<String, Integer>> logList = new ArrayList<>(hashMap.entrySet());
Collections.sort(logList, new Comparator<Entry<String, Integer>>() {
    @Override
    public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
        return o2.getKey().compareTo(o1.getKey());
    }
});

CodePudding user response：

You have to use Java Stream Api for solve this problem.

hashmap.entrySet()
       .stream()
       // "Map.Entry.comparingByValue())" is convert HashMap value into ascending order by default
       // "Collections.reverseOrder()" is convert HashMap value into reverse of ascending order(descending)
       .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
       // print the hashmap
       .forEach(entry -> System.out.println(entry.getKey()    ": "   entry.getValue()));