Searching for all numbers in an array with maximum frequency?

Question

I am trying to figure out all the numbers with the maximum frequency. ie If the maximum frequency is 5, then I need all the numbers that happened 5 times in the array.

consider the following array example:

1 8 7 8 9 2 1 9 6 4 3 5

Here the most frequent numbers are 8, 1, 9 with a maximum frequency of 2. My expected result looks something like this:

8 => 2
1 => 2
9 => 2

In my project, I am trying to figure out the most common numbers and the least frequent numbers. Here I need only the most frequent numbers.

I created 1000 random numbers similar to my project scenario, and calculated the various numbers and then their appearance.

    int n=100;
    int N=1000;

    int data[] = new int[N];
    Set<Integer> set = new HashSet<Integer>();

    Random random = new Random();

    for(int i=0;i<N;i++){
        int  number = random.nextInt(n);
        data[i] = number;
        set.add(number);
    }

    int frequency[] = new int[set.size()];
    Integer[] distinct = set.toArray(new Integer[set.size()]);

    for (int j=0;j<set.size();j++){
        int count=0;
        for(int k=0;k<N;k++){
            if(distinct[j]==data[k]){
                count = count+1;
            }
        }
        frequency[j] = count;
    }

After calculating the frequencies of each number, I calculated the numbers with most frequencies using the answer here , which is optimized.

    int max = Integer.MIN_VALUE;
    List<Integer> vals = new ArrayList<>();

    for (int q=0; q < frequency.length; ++q) {

        if (frequency[q] == max) {
            vals.add(q);
        }

        else if (frequency[q] > max) {
            vals.clear();
            vals.add(q);
            max = frequency[q];
        }
    }

    for(int num : vals){
        System.out.println(distinct[num]+" => "+frequency[num]);
    }

. .

, .

?   - ?

.

Answer 1

. , ? O (N).

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Test {
public static void main(String[] args) {
    int[] A = { 1, 8, 7, 8, 9, 2, 1, 9, 6, 4, 3, 5, 4, 4, 4, 4, 4 };
    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    for (int i : A) {
        if (map.containsKey(i)) {
            map.put(i, map.get(i) + 1);
        } else {
            map.put(i, 1);
        }
    }
    System.out.println(sortByValue(map));
    List<Integer> keys = new ArrayList<Integer>(sortByValue(map).keySet());
    int maximumPossibleFrequency = map.get(keys.get(keys.size() - 1));
    for (int i = keys.size() - 1; i >= 0; i--) {
        if (map.get(keys.get(i)) < maximumPossibleFrequency) {
            break;
        } else {
            System.out.println(keys.get(i) + " => " + map.get(keys.get(i)));
        }
    }
}

public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> unsortMap) {

    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(unsortMap.entrySet());

    Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }

    return result;

}
}

Answer 2

. , , , , .

    Map<Integer, Long> frequencies = Arrays.stream(data)
            .boxed()
            .collect(Collectors.groupingBy(i -> i, Collectors.counting()));
    if (frequencies.isEmpty()) {
        System.out.println("No data");
    } else {
        long topFrequency = frequencies.values()
                .stream()
                .max(Long::compareTo)
                .get();
        int[] topNumbers = frequencies.entrySet()
                .stream()
                .filter(e -> e.getValue() == topFrequency)
                .mapToInt(Map.Entry::getKey)
                .toArray();
        for (int number : topNumbers) {
            System.out.println("" + number + " => " + topFrequency);
        }
    }

( ):

1 => 2
8 => 2
9 => 2

: tucuxi : ? , , :

        frequencies.entrySet()
                .stream()
                .filter(e -> e.getValue() == topFrequency)
                .mapToInt(Map.Entry::getKey)
                .forEach(n -> System.out.println("" + n + " => " + topFrequency));

, , . , OP , , , , . , , , . , .

Answer 3

O(n^2) .

for, Map<Integer,Integer>, - , , - .

, Map, ( Map). O(n).

int maxFreq = Integer.MIN_VALUE;
Map<Integer,Integer> freqs = new HashMap<>();
for(int i=0;i<N;i++){
    int number = random.nextInt(n);
    data[i] = number;
    Integer freq = freqs.get(number);
    if (freq != null) {
        freq = freq + 1;
    } else {
        freq = 1;
    }
    freqs.put(number,freq);
    if (freq > maxFreq)
        maxFreq = freq;
}
for(Map.Entry<Integer,Integer> entry : freqs.entrySet()) {
    if (entry.getValue().equals(maxFreq)) {
        System.out.println(entry.getKey() +" => "+ maxFreq);
    }
}

Answer 4

Java8. . :

 public static void main(String[] args) {
    List<Integer> integers = Arrays.asList(1, 8, 7, 8, 9, 2, 1, 9, 6, 4, 3, 5);
    //Here we have statistics of frequency for all numbers
    LinkedHashMap<Integer, Integer> statistics = integers.stream().distinct()
        .collect(Collectors.toMap(Function.identity(), number -> Collections.frequency(integers, number)))
        .entrySet().stream().sorted(Collections.reverseOrder(Comparator.comparing(Map.Entry::getValue)))
        .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (o1, o2) -> o1, LinkedHashMap::new));
    //Calculate max frequency
    Integer maxFrequency = statistics.entrySet().stream()
        .max(Comparator.comparingInt(Map.Entry::getValue))
        .map(Map.Entry::getValue).orElse(null);
    //Collect max frequent numbers to a map
    Map<Integer, Integer> topFrequentNumbers = statistics.entrySet().stream()
        .filter(o -> o.getValue().equals(maxFrequency))
        .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
    //Print
    topFrequentNumbers.forEach((number, frequency) -> System.out.println(number + " => " + frequency));
}

:

1 => 2
8 => 2
9 => 2

, .

Answer 5

, (O(n), ) . , . , , , , , , " ". , .

   public static ArrayList<Integer> mostFrequent(int [] numbers) {
        HashMap<Integer, Integer> frequencies = new HashMap<>();
        ArrayList<Integer> mostFrequent = new ArrayList<>();
        int greatestFrequency = 0;
        for (int n : numbers) {

            // build number -> frequency of number map
            int f = frequencies.getOrDefault(n, 0) + 1;
            frequencies.put(n, f);

            if (f > greatestFrequency) {
                // this number is more frequent than all others:
                //  it is now the sole, most frequent, number: no ties
                mostFrequent.clear();
                greatestFrequency = f;
            }
            if (f == greatestFrequency) {
                // this number is as frequent as the most frequent:
                //  add it to the list of numbers tied for this privilege
                mostFrequent.add(n);
            }
        }

        // print out the final list of numbers that are tied for "most frequent"
        for (int n : mostFrequent) {
            System.out.println(n + " => " + greatestFrequency);
        }
    }

, null . . Iterable<Number>, . , OP .