找到数组中出现次数最多的元素
我必须找到双数组中出现次数最多的元素。 我是这样做的：
int max = 0; for (int i = 0; i < array.length; i++) { int count = 0; for (int j = 0; j = max) max = count; } 该程序有效，但太慢了！ 我必须找到更好的解决方案，任何人都可以帮助我吗？
更新：
- 正如Maxim指出的那样，使用HashMap比Hashtable更合适。
- 这里的假设是你不关心并发性。 如果需要同步访问，请改用ConcurrentHashMap 。
您可以使用HashMap计算双数组中每个唯一元素的出现次数，并且：
- 以线性O（n）时间运行，并且
- 需要O（n）空间
Psuedo代码将是这样的：
- 迭代一次数组的所有元素： O（n）
- 对于访问过的每个元素，检查其密钥是否已存在于HashMap： O（1）中，已分摊
- 如果没有（第一次看到这个元素），那么将它作为[key：this element，value：1]添加到HashMap中。 O（1）
- 如果确实存在，则将对应于该键的值递增1. O（1），摊销
- 完成构建HashMap后，遍历地图并找到具有最高关联值的键 – 这是出现次数最多的元素。 上）
部分代码解决方案 ，让您了解如何使用HashMap：
import java.util.HashMap; ... HashMap hm = new HashMap(); for (int i = 0; i < array.length; i++) { Double key = new Double(array[i]); if ( hm.containsKey(key) ) { value = hm.get(key); hm.put(key, value + 1); } else { hm.put(key, 1); } }
我将留下作为练习，以便在之后迭代HashMap以找到具有最高值的键; 但如果你遇到困难，只需添加另一条评论，我会给你更多提示=）
我会建议另一种方法。 我不知道这是否会更快。
快速排序数组。 使用内置的Arrays.sort（）方法。
现在比较相邻的元素。 考虑这个例子：
1 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 9 9 9 10 10 10 29 29 29 29 29 29
当相邻元素不相等时，您可以停止计算该元素。
使用Collections.frequency选项：
List list = Arrays.asList("1", "1","1","1","1","1","5","5","12","12","12","12","12","12","12","12","12","12","8"); int max = 0; int curr = 0; String currKey = null; Set unique = new HashSet (list); for (String key : unique) { curr = Collections.frequency(list, key); if(max < curr){ max = curr; currKey = key; } } System.out.println("The number " + currKey + " happens " + max + " times");
输出：
The number 12 happens 10 times
public static void main(String[] args) { int n; int[] arr; Scanner in = new Scanner(System.in); System.out.println("Enter Length of Array"); n = in.nextInt(); arr = new int[n]; System.out.println("Enter Elements in array"); for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int greatest = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > greatest) { greatest = arr[i]; } } System.out.println("Greatest Number " + greatest); int count = 0; for (int i = 0; i < arr.length; i++) { if (greatest == arr[i]) { count++; } } System.out.println("Number of Occurance of " + greatest + ":" + count + " times"); in.close(); }
您可以在一个循环中解决此问题，而无需使用HashMap或O（1）空间复杂度中的任何其他数据结构。
初始化两个变量count = 0和max = 0（如果数组中有负数，则初始化为Integer.MIN_VALUE）
我的想法是你将扫描数组并检查当前的数字，
- 如果它小于你当前的最大值……那么什么也不做
- 如果它等于你的最大值…则递增计数变量
- 如果它大于你的max..then update max to current number并将count设置为1
码：
int max = 0, count = 0; for (int i = 0; i < array.length; i++) { int num = array[i]; if (num == max) { count++; } else if (num > max) { max = num; count = 1; } }
继续使用您编写的伪代码，请尝试下面编写的代码： –
public static void fetchFrequency(int[] arry) { Map newMap = new TreeMap(Collections.reverseOrder()); int num = 0; int count = 0; for (int i = 0; i < arry.length; i++) { if (newMap.containsKey(arry[i])) { count = newMap.get(arry[i]); newMap.put(arry[i], ++count); } else { newMap.put(arry[i], 1); } } Set> set = newMap.entrySet(); List> list = new ArrayList>(set); Collections.sort(list, new Comparator>() { @Override public int compare(Entry o1, Entry o2) { return (o2.getValue()).compareTo(o1.getValue()); } }); for (Map.Entry entry : list) { System.out.println(entry.getKey() + " ==== " + entry.getValue()); break; } //return num; }
解决方案1：使用HashMap
class test1 { public static void main(String[] args) { int[] a = {1,1,2,1,5,6,6,6,8,5,9,7,1}; // max occurences of an array Map map = new HashMap<>(); int max = 0 ; int chh = 0 ; for(int i = 0 ; i < a.length;i++) { int ch = a[i]; map.put(ch, map.getOrDefault(ch, 0) +1); }//for Set> entrySet =map.entrySet(); for(Entry entry : entrySet) { if(entry.getValue() > max) {max = entry.getValue();chh = entry.getKey();} }//for System.out.println("max element => " + chh); System.out.println("frequency => " + max); }//amin } /*output => max element => 1 frequency => 4 */
解决方案2：使用count数组
public class test2 { public static void main(String[] args) { int[] a = {1,1,2,1,5,6,6,6,6,6,8,5,9,7,1}; int max = 0 ; int chh = 0; int count[] = new int[a.length]; for(int i = 0 ; i max) {max = count[ch] ; chh = ch ;} }//for System.out.println(chh); }//main }