我必须在双数组中找到出现次数最多的元素。我是这样做的：
int max = 0;
for (int i = 0; i < array.length; i++) {
int count = 0;
for (int j = 0; j < array.length; j++) {
if (array[i]==array[j])
count++;
}
if (count >= max)
max = count;
}
程序可以运行，但是太慢了！我必须找到更好的解决方案，有人可以帮助我吗？
更新：
您可以使用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 以找到具有最高值的键；但如果你遇到困难，只需添加另一条评论，我会给你更多提示 =)
使用Collections.frequency选项：
List<String> 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<String> unique = new HashSet<String>(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
Java 8 的解决方案
int result = Arrays.stream(array)
.boxed()
.collect(Collectors.groupingBy(i->i,Collectors.counting()))
.values()
.stream()
.max(Comparator.comparingLong(i->i))
.orElseThrow(RuntimeException::new));
我会建议另一种方法。我不知道这是否会更快。
快速排序数组。使用内置的 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
当相邻元素不相等时，您可以停止计算该元素。
解决方案 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<Integer,Integer> 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<Entry<Integer,Integer>> entrySet =map.entrySet();
for(Entry<Integer,Integer> 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：使用计数数组
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 <a.length ; i++) {
int ch = a[i];
count[ch] +=1 ;
}//for
for(int i = 0 ; i <a.length ;i++) {
int ch = a[i];
if(count[ch] > max) {max = count[ch] ; chh = ch ;}
}//for
System.out.println(chh);
}//main
}
这是一个Java解决方案-
List<Integer> list = Arrays.asList(1, 2, 2, 3, 2, 1, 3);
Set<Integer> set = new HashSet(list);
int max = 0;
int maxtemp;
int currentNum = 0;
for (Integer k : set) {
maxtemp = Math.max(Collections.frequency(list, k), max);
currentNum = maxtemp != max ? k : currentNum;
max = maxtemp;
}
System.out.println("Number :: " + currentNum + " Occurs :: " + max + " times");
int[] array = new int[] { 1, 2, 4, 1, 3, 4, 2, 2, 1, 5, 2, 3, 5 };
Long max = Arrays.stream(array).boxed().collect(Collectors.groupingBy(i -> i, Collectors.counting())).values()
.stream().max(Comparator.comparing(Function.identity())).orElse(0L);
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();
}
继续您编写的伪代码，请尝试以下编写的代码：-
public static void fetchFrequency(int[] arry) {
Map<Integer, Integer> newMap = new TreeMap<Integer, Integer>(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<Entry<Integer, Integer>> set = newMap.entrySet();
List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(set);
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});
for (Map.Entry<Integer, Integer> entry : list) {
System.out.println(entry.getKey() + " ==== " + entry.getValue());
break;
}
//return num;
}
这就是我在java中实现的方式..
import java.io.*;
class Prog8
{
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Input Array Size:");
int size=Integer.parseInt(br.readLine());
int[] arr= new int[size];
System.out.println("Input Elements in Array:");
for(int i=0;i<size;i++)
arr[i]=Integer.parseInt(br.readLine());
int max = 0,pos=0,count = 0;
for (int i = 0; i < arr.length; i++)
{
count=0;
for (int j = 0; j < arr.length; j++)
{
if (arr[i]==arr[j])
count++;
}
if (count >=max)
{
max = count;
pos=i;
}
}
if(max==1)
System.out.println("No Duplicate Element.");
else
System.out.println("Element:"+arr[pos]+" Occourance:"+max);
}
}
您可以在一个循环中解决此问题，而无需使用 HashMap 或 O(1) 空间复杂度的任何其他数据结构。
初始化两个变量 count = 0 和 max = 0（如果数组中有负数，则初始化 Integer.MIN_VALUE）
这个想法是您将扫描数组并检查当前数字，
代码：
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;
}
}
这是 Ruby 解决方案：
def maxOccurence(arr)
m_hash = arr.group_by(&:itself).transform_values(&:count)
elem = 0, elem_count = 0
m_hash.each do |k, v|
if v > elem_count
elem = k
elem_count = v
end
end
"#{elem} occured #{elem_count} times"
end
p maxOccurence(["1", "1","1","1","1","1","5","5","12","12","12","12","12","12","12","12","12","12","8"])
输出：
"12 occured 10 times"