增强Java中获取数组中元素最高出现次数的方法

Question

我在一次面试中遇到了以下问题。

问:你需要找到数组中最频繁的元素。该数组由整数组成。例如，如果你有一个这样的整数序列: 1，2，9，3，4，3，3，1，2，4，5，3，8，3，9，0，3，2，字符串：

获胜者是3号，出现频率是6

这个问题的答案在面试过程中得到了改进。

以下是源码：

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class RepeatedElement {

public static void main(String[] args) {
    int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    
    Arrays.sort(arr);
    
    int len = arr.length;
    
    int count = 1;
    
    Map<Integer,Integer> map = new TreeMap<>();
    
    int i=0;
    while(i < len) {
        for(int j=i+1;j<len;j++) {
            if(arr[i]==arr[j]) {
                count++;
                i++;
            }else {
                break;
            }
        }
        map.put(arr[i], count);
        count = 1;
        i++;
    }
    
        
    int max = 0;
    int key = 0;
    for(int k:map.keySet()) {
        int temp = map.get(k);
        
        if(temp>max) {
            max = temp;
            key = k;
        }
    }
    
    System.out.println("Winner is: "+key+" and it's occurrences: "+max);
}
}

我还在stackoverflow中搜索了其他类似的问题。我只是想知道这是否是解决这个问题的好方法。我相信代码能更好地解释我尝试过的方法。同时，我很想知道时间和空间的复杂性，这将提供更大的输入。朋友们，如果这段代码有一些缺陷，请提供你们的想法来改进它。提前谢谢。

Answer 1

您可以使用Map中的compute函数将第一个循环简化为如下所示：

    for (int i=0; i < arr.length; i++) {
        map.compute(arr[i], (k,v) -> v == null ? 1 : v+1);
    }

或者，如果您向第三方库开放，您可以使用Eclipse Collections中的Bag类型，并将整个方法替换为以下内容：

public static void main(String[] args) {
    Integer[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    MutableBag<Integer> bag = Bags.mutable.of(arr);
    ObjectIntPair<Integer> top = bag.topOccurrences(1).getFirst();
    System.out.println("Winner is: "+top.getOne()+" and it's occurrences: "+ top.getTwo());
}

甚至还有一种PrimitiveBag类型来避免int的装箱

public static void main(String[] args) {
    int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    MutableIntBag bag = IntBags.mutable.of(arr);
    IntIntPair top = bag.topOccurrences(1).getFirst();
    System.out.println("Winner is: "+top.getOne()+" and it's occurrences: "+ top.getTwo());
}

Answer 2

从代码中的map.put(arr[i], count);语句看，您似乎没有意识到可以使用现有值来更新映射中的现有键。这就是为什么似乎要通过遍历所有的键来计算元素的原因。只要再次看到密钥，就可以使用map.put(arr[i], map.get(arr[i]) + 1)更新密钥的计数。

此外，您也不需要再次迭代地图的keySet来获得最大频率，您可以在填充地图本身时获得最大频率。

代码将为：

    public static void main(String args[]) {
      int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
      Map<Integer,Integer> map = new HashMap<>();
      int max = 1;
      int maxKey = arr[0];
      for ( int k : arr ) {
          map.put(k, map.getOrDefault(k, 0) + 1);
          if ( map.get(k) > max ) {
              max = map.get(k);
              maxKey = k;
          }
      }
      System.out.println("Winner is: "+ maxKey+" and it's occurrences: "+max);
   }

Answer 3

您正在执行排序：不需要引入时间复杂度>= O(NLogN)。

也不需要使用TreeMap。使用HashMap将get或put操作减少为常量，而不是log(N)。

您可以将两个循环合并为一个循环()。

解决方案的复杂性如下：

1. 下面代码中的时间复杂度是O(N)。
2. 空间复杂度是O(N)。

使用 (Java 8+)递增现有的频率计数。这样你就不需要

1. 首先获取现有值，
2. 检查该值是否存在，如果存在，则将其递增，如果不存在，则将其设置为1。

您也可以使用 (Java 8+)操作。

合并和计算的示例在下面的代码中进行了说明。

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class MostFrequentElementInArray {

    public static void main(String[] args) {
    int[] arr = { 1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2 };

    int len = arr.length;


    int mostFreqKey = arr[0];

    Map<Integer, Integer> map = new HashMap<>();

    for (int elem : arr) {
        // you can use any of the 3:
        int newVal = map.compute(elem, (K, oldVal) -> oldVal == null ? 1 : oldVal + 1  );
        // int newVal = map.merge(elem, 1, (oldVal, valWhichIs1) -> oldVal + valWhichIs1);
        // int newVal = map.merge(elem, 1, Integer::sum);
        if (map.get(mostFreqKey) < newVal) {
            // this is the new frequently occurring element
            mostFreqKey = elem;
        }
        
        
    }
    
    
    
    System.out.println("Winner is: " + mostFreqKey + " and it's occurrences: " + map.get(mostFreqKey));
    }
}