java查找最大最频繁元素

Question

我在Java中有一个值为的ArrayList

4, 4, 3, 3, 5, 6

我需要找到最频繁的值。如果多个值的出现次数相同，则返回最大值

在上面的例子中，我需要返回值4

private int getFrequentNumber(ArrayList<Integer> arr){
    int popular = arr.get(0);
    int count = 1;
    int tempcount = 0;
    int temp = 0;

    for(int i = 0; i < arr.size(); i++) {
        temp = arr.get(i);
        tempcount = 0;
        for(int j = 1; j < arr.size(); j++) {
            if(temp == arr.get(j))
                tempcount++;
        }
        if (tempcount > count) {
            popular = temp;
            count = tempcount;
        }
    }
    return popular;
}

现在我有这个代码，所以它返回最频繁的数字，但我需要帮助返回最大最频繁的数字

Answer 1

public int getPopularElement(ArrayList<Integer> arr) {
    int count = 1, tempCount;
    int popular = arr.get(0);
    int temp = 0;
    for (int i = 0; i < (arr.size()- 1); i++) {
         temp = a.get(i);
         tempCount = 0;
         for (int j = 1; j < arr.length; j++) {
             if (temp == arr.get(j))
                 tempCount++;
         }
         if (tempCount >= count && temp>popular ) {
             popular = temp;
             count = tempCount;
         }
         if (tempCount > count) {
             popular = temp;
             count = tempCount;
         }
     }
     return popular;
}

第二种方法是按照@triffic的说法对数据进行排序，但速度较慢（我想还是按照相同的顺序？）

您只需对数组进行排序即可

  Collections.sort(arr);

你的代码

private int getFrequentNumber(ArrayList<Integer> arr) {
        Collections.sort(arr);
        int popular = arr.get(0);
        int count = 1;
        int tempCount ;
        int temp ;

        for (int i = 0; i < arr.size(); i++) {
            temp = arr.get(i);
            tempCount = 0;
            for (int j = 1; j < arr.size(); j++) {
                if (temp == arr.get(j))
                    tempCount++;
            }
            if (tempCount > count) {
                popular = temp;
                count = tempCount;
            }
        }
        return popular;
    }

Answer 2

一种简单的方法是使用地图跟踪频率：

Map<Integer, Integer> freq = new HashMap<>();
int maxCnt = 0;
int maxNum = 0;

for (int num : arr) {
    int cnt = freq.get(num) == null ? 1 : freq.get(num) + 1;
    if (cnt > maxCnt || (cnt == maxCnt && num > maxNum)) {
        maxCnt = cnt;
        maxNum = num;
    }
    freq.put(num, cnt);
}

if (arr.size() > 0) {
    System.out.println("The number " + maxNum + " occurred " + maxCnt + " times.");
}
else {
    System.out.println("There were no numbers available.");
}

Demo

Answer 3

使用列表上的流，可以根据条目的频率（计数收集器）对条目进行分组，然后找到最大频率。下面的比较器只是在频率相等时比较键（实际条目）（用于查找最高值

List<Integer> arr = Arrays.asList(4, 4, 3, 3, 5, 6);

Entry<Integer, Long> maxEntry = arr.stream()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet()
        .stream()
        .max(
                (e1, e2) -> 
                   e1.getValue() == e2.getValue() 
                     ?
                   Long.compare(e1.getKey(), e2.getKey())
                     :
                   Long.compare(e1.getValue(), e2.getValue())  
         )
        .get();

System.out.println(String.format("Most frequent key: %s. Frequency: %s", 
        maxEntry.getKey(), maxEntry.getValue()));

这个的输出是

Most frequent key: 4. Frequency: 2

Answer 4

步骤1：对ArrayList<Integer> arr进行快速排序

步骤2：在ArrayList<Integer> arr上进行迭代，正如您所做的那样

Answer 5

那些不想重新发明自行车的人可能会使用带有MultiSet集合的Guava库，该集合保存元素（在本例中为整数）及其频率

    Multiset<Integer> myMultiset = HashMultiset.create(listOfElements);

    // Returns a copy of multiset as an ImmutableMultiset whose iteration order is highest frequency first
    ImmutableMultiset<Integer> integersOrderedByFrequency = Multisets.copyHighestCountFirst(myMultiset);
    int intWithHighestFrequency = integersOrderedByFrequency.iterator().next();
    int highestFrequency = myMultiset.count(intWithHighestFrequency);

    // Now we should find the largest Integer among those with the highest frequency
    OptionalInt maxValueOpt = myMultiset.entrySet().stream()
            .filter(entry -> entry.getCount() == highestFrequency)
            .mapToInt(Multiset.Entry::getElement)
            .max();

    System.out.println(maxValueOpt.getAsInt()); 

或类似的解决方案：

    Multiset<Integer> myMultiset = HashMultiset.create(listOfElements);

    Optional<Integer> result = myMultiset.entrySet().stream()
            .sorted((a, b) -> {
                // If count is higher for the first element - rank it higher in the list
                if (a.getCount() > b.getCount()) {
                    return -1;
                // If count is lower for the first element - rank it lower in the list
                } else if (a.getCount() < b.getCount()) {
                    return 1;
                //If element counts are the same - the element with the higher value will be ranked higher
                } else {
                    return b.getElement() - a.getElement();
                }
            })
            .map(Multiset.Entry::getElement)
            .findFirst();

    System.out.println(result.get());

Answer 6

您可以创建一个数组来存储这些数字的频率。计算完所有频率后，返回基于此数组的最大频率数

private static int getFrequentNumber(ArrayList<Integer> arr){
    int tempcount = 0;
    int temp = 0;

    int[] frequency = new int[arr.size()];

    for(int i = 0; i < arr.size(); i++) {
        temp = arr.get(i);
        tempcount = 0;
        for(int j = 0; j < arr.size(); j++) {
            if(temp == arr.get(j))
                tempcount++;
        }
        frequency[i] = tempcount;
    }

    int maxIndex = 0;
    for (int i = 0; i < frequency.length; i++) {
        if (frequency[i] >= frequency[maxIndex] && arr.get(i) > arr.get(maxIndex)) {
            maxIndex = i;
        }
    }
    return arr.get(maxIndex);
}