寻找数组中所有出现频率最高的数字?

4
我正在尝试查找所有最频繁出现的数字。例如,如果最高出现频率为5,则需要找到所有在数组中出现5次的数字。
让我们考虑以下数组示例:
1 8 7 8 9 2 1 9 6 4 3 5
在这里,最频繁出现的数字是8、1和9,它们的出现频率最高为2。我的期望输出结果如下:
8 => 2
1 => 2
9 => 2

在我的项目中,我试图找出最频繁的数字和最不频繁的数字。这里我只想要最频繁的数字。
我已经生成了1000个随机数,与我的项目场景类似,并计算了独特数字及其出现次数。
    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;
    }

计算每个数字的频率后,我使用这里提供的优化答案来计算具有最高频率的数字。

    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]);
    }

在第一段代码中,循环使整个过程变得更慢。这只是庞大代码和示例测试用例的一部分。

我希望能够加快处理速度,因为在实际情况下数组中可能会有很多元素。

是否有优化这些循环的方法? 或者 其他获取结果的方式?

非常感谢任何形式的帮助。


你能试着用我下面回答的代码来工作吗?应该没问题的。 - murasing
5个回答

5
我会为此使用流。虽然并不会更短,但一旦您熟悉了流,它在概念上会更简单。
    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需要存储最高频率的数字,所以我演示了如何做到这一点,并仅打印它们以显示结果。有些人认为流应该没有副作用,而我认为向标准输出打印是一种副作用。但如果您喜欢,可以使用它。


啊,抱歉,我没好好读那三个单词。当然,如果你想要,这段代码就是你项目的了。 - Ole V.V.
我不是Java高级组件方面的专家。所以,我已经问过了:D - Sagar Gautam

3
该代码非常低效,最坏情况下可能以O(n^2)运行。
你可以通过使用单个for循环构建一个Map来实现目标,其中键是您遇到的每个唯一数字,值是其频率。
在您拥有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);
    }
}

2

这应该会对您有所帮助。完美优化的代码,猜猜怎么着?它以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;

}
}

1
大型数组的性能不错。你能解释一下上面代码的逻辑和流程吗? - Sagar Gautam
@Sagar,正如你所看到的,这个方法sortByValue是用来根据它的值对map进行排序的,而且请注意,我是从底部向上扫描map,将高频率到低频率的顺序记在心中。再次,临时变量maximumPossibleFrequency被赋予了map中最高可能的频率,现在我相信你可以自己解决剩下的问题 :) 顺便说一句,如果你觉得这个回答解决了你的问题,请将其标记为已接受的答案,谢谢。 - murasing
@tucuxi 是的,你的理由很有道理,我同意。但是“object”这个词有点过于强烈了,我相信你可以用更友善的方式来反驳。干杯! - murasing
1
@murasing - 我看到你已经修复了代码,所以我已经删除了评论。不是因为措辞问题,因为它并不是有意冒犯;这是我能找到的最好的方式来指出可以改进的地方--但是因为问题现在已经解决,这对答案是有益的。恭喜你获得了接受! - tucuxi

1

我会使用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

正如我之前提到的,您可以使用并行流和提取一些片段来提高性能。

比OleV的答案复杂得多,而且也是基于流的。 - tucuxi
@tucuxi,你是对的。我的方法更复杂。我也喜欢OleV的回答方式。 - dvelopp

1
我认为这是最简单和最优的答案(对于这个问题是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不想在生产系统中使用它。

谢谢您的回复,这与我想要的“小而优化”的相似,但是我不知道它是如何工作的。 - Sagar Gautam
1
我已经加了注释。一般来说,它不是在最后查看频率,而是实时更新“最常见”标题(以及该标题的并列列表)。 - tucuxi
只需一个循环流程,太棒了。 - Sagar Gautam

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接