logo标签列表

在Java中编写一种方法，以查找数组中出现频率最高的元素。

javaarraysmethodsmode
16

问题是:

编写一个名为mode的方法，该方法返回整数数组中出现频率最高的元素。假设数组至少有一个元素，并且数组中的每个元素的值介于0和100之间（包括0和100）。在选择最高频率元素时，如果存在多个元素，选择其中值较小的元素。

例如，如果传递的数组包含值{27, 15, 15, 11, 27}，则您的方法应返回15。（提示：您可能希望查看本章前面的Tally程序，以了解如何解决此问题。）

下面是我的代码，它几乎可以正常工作，除了单个元素的数组：

public static int mode(int[] n)
{
    Arrays.sort(n);
    
    int count2 = 0;
    int count1 = 0;
    int pupular1 =0;
    int popular2 =0;
    
    
    for (int i = 0; i < n.length; i++)
    {
            pupular1 = n[i];
            count1 = 0;    //see edit
        
        for (int j = i + 1; j < n.length; j++)
        {
            if (pupular1 == n[j]) count1++;
        }
        
        if (count1 > count2)
        {
                popular2 = pupular1;
                count2 = count1;
        }
        
        else if(count1 == count2)
        {
            popular2 = Math.min(popular2, pupular1);
        }
    }
    
    return popular2;
}

编辑：最终弄清楚了。将count1 = 0;更改为count1 = 1;，现在一切都正常了！

3
在提问之前对好的工作进行加1评价（几乎可以胜任，除了单元素数组的情况）。你能否将你的解决方案发布为答案并将其标记为正确？这样其他人就不会来到你的问题帮助你，认为它还没有被回答。谢谢。 - Simon
我赞同@Simon的评论，并补充说目前被接受的答案（Gubatron的）是有缺陷和不正确的。例如，它将无法处理示例输入{27，15，15，11，27}。 counts的长度为5，行counts [n [I]] ++将失败，因为它将尝试增加索引为27的元素，如shridhad在评论中指出的越界了。 - phoog
我同意Simon的看法，您能把编辑好的解决方案移动到下面的回答中吗？我们喜欢在这里使用问答格式。 - halfer
1
回顾这个问题，五年后的今天，我惊讶于自己的成长。那时候，我刚开始转行计算机科学，对于像 map 和 set 这样的数据结构一无所知。在学习和工作中，我通过几乎蛮力的方法探索了高效的算法。这改变了我的人生 :) - TonyGW
14个回答
13

对于这样的问题，您应该使用哈希映射表。将每个元素放入哈希映射表中需要O(n)时间，而获取元素只需要O(1)时间。在给定的代码中，我基本上是取一个全局最大值并将其与从哈希映射表中收到的值进行比较，每次输入一个元素时，请看：

哈希映射表有两部分，一部分是键(key)，另一部分是值(value)，当您对键执行get操作时，返回其对应的值。

public static int mode(int []array)
{
    HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
    int max  = 1;
    int temp = 0;

    for(int i = 0; i < array.length; i++) {

        if (hm.get(array[i]) != null) {

            int count = hm.get(array[i]);
            count++;
            hm.put(array[i], count);

            if(count > max) {
                max  = count;
                temp = array[i];
            }
        }

        else 
            hm.put(array[i],1);
    }
    return temp;
}
如果所有元素都是唯一的，那你确定我们能找到结果吗？ - Debopam Mitra
3
如果所有元素都是独一无二的，那么就没有经常出现的元素 :) - codemania23
1
如果所有元素都是唯一的，那么所有项的频率均为1，并且都是众数的候选项。根据问题描述，最小的元素将是众数。 - Abhilash Kishore
@AbhilashKishore 确实，这不是代码的功能。如果所有元素都是唯一的，则模式返回0，也就是初始temp值。要解决这个问题，需要修改代码并在return之前添加一行，如下所示：if(temp == 0) temp = array[(int)(Math.random() * array.length)];。这样就会选择一个随机值。 - BestDogeStackoverflow
3

您应该能够在N个操作内完成此操作，也就是说，在一次遍历中，O(n)时间内。

使用map或int[]（如果问题仅针对int）来增加计数器，并且使用一个变量来保存已看到的最大计数的键。每次您增加计数器时，请询问值是多少并将其与上次使用的键进行比较，如果值更大，请更新键。

public class Mode {
public static int mode(final int[] n) {
    int maxKey = 0;
    int maxCounts = 0;

    int[] counts = new int[n.length];

    for (int i=0; i < n.length; i++) {
        counts[n[i]]++;
        if (maxCounts < counts[n[i]]) {
            maxCounts = counts[n[i]];
            maxKey = n[i];
        }
    }
    return maxKey;
}

public static void main(String[] args) {
    int[] n = new int[] { 3,7,4,1,3,8,9,3,7,1 };
    System.out.println(mode(n));
}
}
对不起，请问"counts[n[i]]++;"是什么意思？ - TonyGW
将n[i]的出现次数增加1。 - Gubatron
6
如果 int[] n = new int[]{12, 13, 13};，将会抛出 ArrayIndexOutOfBoundsException。因此，这个解决方案只在数组中的每个数字都小于数组长度时才有效。 - shriidhar
2
请注意，这不是正确的实现方式，因为数组可能包含1-100个整数，而counts [n [i]]会溢出。此外，只有在整数周围有边界的情况下才有用。 - Matej Briškár
2
@shridhad 除了你提供的例子之外，这个解决方案在问题中给出的例子{27, 15, 15, 11, 27}上也会失败。 - phoog
1
如果数组中给定的值超过了数组长度，就会抛出ArrayOutOfBounds异常。 - cmm user
2
public int mode(int[] array) {
    int mode = array[0];
    int maxCount = 0;
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        int count = 1;
        for (int j = 0; j < array.length; j++) {
            if (array[j] == value) count++;
            if (count > maxCount) {
                mode = value;
                maxCount = count;
            }
        }
    }
    return mode;
}
1

请检查这个... 简述：挑选数组的每个元素并将其与数组的所有元素进行比较，判断它是否等于所选择的元素。

  int popularity1 = 0;
  int popularity2 = 0;
  int popularity_item, array_item; //Array contains integer value. Make it String if array contains string value.
  for(int i =0;i<array.length;i++){
      array_item = array[i];
      for(int j =0;j<array.length;j++){
          if(array_item == array[j])
             popularity1 ++;
          {
      if(popularity1 >= popularity2){
          popularity_item = array_item;
          popularity2 = popularity1;
      }
      popularity1 = 0;
  }
  //"popularity_item" contains the most repeted item in an array.
尝试在一个包含1,000个随机数字的数组上运行此程序。需要多长时间？如果是包含1,000,000个随机数字的数组呢？ - phoog
0

我知道这个问题已经有一段时间了，但我想添加一个答案，我相信可以扩展原始问题。这个问题的补充是编写模式方法，而不依赖预设范围（在这种情况下，0到100）。我编写了一个版本的模式，它使用原始数组中的值范围来生成计数数组。

public static int mode(int[] list) {

    //Initialize max and min value variable as first value of list
    int maxValue = list[0]; 
    int minValue = list[0];

    //Finds maximum and minimum values in list
    for (int i = 1; i < list.length; i++) {
        if (list[i] > maxValue) {
            maxValue = list[i];
        }

        if (list[i] < minValue) {
            minValue = list[i];
        }
    }

    //Initialize count array with (maxValue - minValue + 1) elements  
    int[] count = new int[maxValue - minValue + 1];

    //Tally counts of values from list, store in array count
    for (int i = 0; i < list.length; i++) {
        count[list[i] - minValue]++; //Increment counter index for current value of list[i] - minValue
    }

    //Find max value in count array
    int max = count[0]; //Initialize max variable as first value of count

    for (int i = 1; i < count.length; i++) {
        if (count[i] > max) {
            max = count[i];
        }
    }

    //Find first instance where max occurs in count array
    for (int i = 0; i < count.length; i++) {
        if (count[i] == max) {
            return i + minValue; //Returns index of count adjusted for min/max list values - this is the mode value in list
        }
    }
    return -1; //Only here to force compilation, never actually used
}
0

这是我的答案。

public static int mode(int[] arr) {
    int max = 0;
    int maxFreq = 0;

    Arrays.sort(arr);
    max = arr[arr.length-1];

    int[] count = new int[max + 1];

    for (int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

     for (int i = 0; i < count.length; i++) {
        if (count[i] > maxFreq) {
            maxFreq = count[i];
        }
    }

    for (int i = 0; i < count.length; i++) {
        if (count[i] == maxFreq) {
            return i;
        }
    }
    return -1;
}
如果数组arr中包含负值，则此操作将失败。如果数组包含像2,147,483,647这样非常大的值，您也可能会遇到问题。 - phoog
0

在这里，我使用了单个循环进行编码。我们从a[j-1]获取模式，因为当j为j-1时，localCount最近被更新。此外，N是数组的大小，计数器初始化为0。

        //After sorting the array 
        i = 0,j=0;
        while(i!=N && j!=N){
            if(ar[i] == ar[j]){
                localCount++;
                j++;
            }
            else{
                i++;
                localCount = 0;
            }
            if(localCount > globalCount){
                globalCount = localCount;
                mode = ar[j-1]; 
            }
        }
0
    Arrays.sort(arr);
    int max=0,mode=0,count=0;
    for(int i=0;i<N;i=i+count) {
        count = 1;
        for(int j=i+1; j<N; j++) {
            if(arr[i] == arr[j])
                count++;
        }
        if(count>max) {
            max=count;
            mode = arr[i];
        }
    }
0

这不是最快的方法，但如果您不想涉及HashMap并且想避免使用2个for循环来解决复杂性问题，那么这种方法相当简单易懂...

    int mode(int n, int[] ar) {
    int personalMax=1,totalMax=0,maxNum=0;

    for(int i=0;i<n-1;i++)
    {

        if(ar[i]==ar[i+1])
        {
            personalMax++;

            if(totalMax<personalMax)
            {
                totalMax=personalMax;
                maxNum=ar[i];
            }
        }    
        else
        {
            personalMax=1;
        }
    }
    return maxNum;
}
0

我会使用这段代码。它包含一个instancesOf函数，并且它会遍历每个数字。

public class MathFunctions {

public static int mode(final int[] n) {
    int maxKey = 0;
    int maxCounts = 0;

    for (int i : n) {
        if (instancesOf(i, n) > maxCounts) {
            maxCounts = instancesOf(i, n);
            maxKey = i;
        }
    }

    return maxKey;
}

public static int instancesOf(int n, int[] Array) {
    int occurences = 0;
    for (int j : Array) {
        occurences += j == n ? 1 : 0;
    }
    return occurences;
}

public static void main (String[] args) {
    //TODO Auto-generated method stub
    System.out.println(mode(new int[] {100,200,2,300,300,300,500}));
}
}

我注意到Gubatron发布的代码在我的电脑上无法运行，它给了我一个ArrayIndexOutOfBoundsException。

这个程序在一个包含1,000,000个元素的数组上运行速度有多快？ - phoog
@phoog，真的非常慢。 - Cornul11
@Cornul11 如果我没记错的话，我是以修辞问题的形式提出了那个问题。 - phoog
@phoog，嗯，那就是我这边的修辞肯定了。 - Cornul11
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接