0

我试图找到在给定的 int 数组中出现最多的数字。这是我的代码，它可以工作，但有一些不一致之处。另外，如果你能让我知道如何让它变得更好，我认为我的代码太长了！！

public static int countOccurrences(int[] a, int x) {
    int count = 0;
    for(int i=0;i<a.length;i++) {
        if(a[i] == x) count++;
    }
    return count;
}

public static int occursMostOften(int[] a) {
    int[] count = new int[a.length];
    boolean[] duplicate = new boolean[a.length];
    for(int i = 0; i < a.length;i++) {
        if(duplicate[i] != true) {
            count[i] = countOccurrences(a,a[i]);
            duplicate[i] = true;
        }
    }
    return a[maxIndex(count)];
}
private static int maxIndex(int[] a) {
    int max = 0;
    for(int i = 1; i<a.length;i++) {
        if(a[i-1]<a[i]) max = i;
    }
    return max;     
}
4

2 回答 2

2

如果这是一个分配（我假设它是），那么您的代码符合要求，尽管不是最佳的。

如果您了解了一种称为 Map 的数据结构，请改用它。映射中的键将是数组中的值，映射中的值是您看到该值的次数。

这将降低代码的复杂性。操作顺序为：

对于数组中的每个值

  1. 如果该值在地图中存在，则更新计数
  2. 如果没有，则创建一个计数为 1 的新条目

最后，您可以遍历地图以找到出现次数最多的值。

于 2012-07-31T10:05:09.467 回答
0

您的代码对每个非重复数字执行完整数组的线性扫描。n对于具有不同值的大小数组，n您的代码复杂度将为 O(n^2)。

您可以使用以下算法在 O(n) 中做得更好：

  • 遍历数组中的所有数字
  • 对于每个数字，将其添加到Map<Integer, Integer>包含数字的地图 () 中并计数
  • 如果地图中存在数字，则获取当前计数，递增并放回地图
  • 如果数字不存在，只需将计数为 1 的条目输入到地图中
  • 在所有迭代完成后，检索值和鳍最大值。
于 2012-07-31T10:07:23.117 回答