Java 中按频率排序元素

10 Sept 2024 | 5 分钟阅读

给定一个整数数组。数组中的一些元素是重复的。我们的任务是返回一个数组或列表，其中包含提供的元素，并按它们出现的频率降序排列。换句话说，出现频率最高的元素应该排在最前面。如果任何两个元素的出现频率相同，则输入数组中先出现的元素应在输出数组中先出现。

示例 1

输入

inputArr[] = {12, 16, 15, 12, 12, 18, 15, 18, 16, 18, 18}

输出

resultArr[] = {18, 18, 18, 18, 12, 12, 12, 16, 16, 15, 15}

解释：元素 18 的出现频率最高，因为它的频率计数为 4。然后，元素 12 的出现频率最高，因为它的频率计数为 3。然后，元素 16 和 15 的频率出现存在平局。由于元素 16 先出现，因此元素 16 排在元素 15 之前。

示例 2

输入

inputArr[] = {19, 20, 17, 45, 34, 3, 2, 1, 89, 56, 80, 85, 90}

输出

resultArr[] = {19, 20, 17, 45, 34, 3, 2, 1, 89, 56, 80, 85, 90}

解释：每个元素的出现频率都相同，即 1。因此，元素在输入数组中的顺序与它们在输出数组中出现的顺序相同。

方法

概念是根据元素出现频率的最高到最低进行排序。为了避免冲突，请根据元素在输入数组中的出现顺序来维护元素的出现索引。

算法

步骤 1：概念是实现自定义比较方法来解决问题。设要比较的两个元素为 'n1' 和 'n2'。那么。

如果 'n1' 和 'n2' 的频率出现不同，则将频率较高的元素放在频率较低的元素之前。
如果 'n1' 和 'n2' 的频率出现相同，则在输入数组中较早出现的元素应放在在输入数组中较晚出现的元素之前。

步骤 2：对于每个元素，将其及其频率和在输入数组中的首次出现索引放入字典中。

步骤 3：根据自定义比较器对元素值进行排序，最终返回具有排列元素的已排序列表。

实施

观察上述算法的实现。

文件名：SortEleByFreq.java

// important import statements
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.Comparator;
class Comparison implements Comparator<ArrayList<Integer>>
{
    public int compare(ArrayList<Integer> al1 , ArrayList<Integer> al2)
    {   
        // frequency of element present in the list al1
        int x1 = al1.get(0);        
        // frequency of element present in the list al2
        int x2 = al2.get(0);
        // index of the first occurrence of the element present in the list al1
        int y1 = al1.get(1);
        // index of the first occurrence of the element present in the list al2
        int y2 = al2.get(1);        
        // if the frequency of occurrence of the elements do not 
        // match return the difference of x2 and x1
        if(x1 != x2)
        {
           return x2 - x1;
        }
        // if the frequency of occurrence of the elements match 
        // return the difference of the indices of their first occurrence 
        else
        {
           return y1 - y2;
        }
    }
}
public class SortEleByFreq 
{
    public int[] sortByFreq(int inputArr[]) 
    {
        HashMap<Integer, Integer> hm = new HashMap<>();
        HashMap<Integer, Integer> idx = new HashMap<>();
        // For each element of the array, put it in the dictionary and its index and frequency of the 
        // first occurrence in the array
        for (int i = 0; i < inputArr.length; i++) 
        {
            if(hm.containsKey(inputArr[i]))
            {   
                // reaching here means, the element inputArr[i]
                // has already been found. Therefore, all we have to 
                // do is to increase its frequency
                hm.put(inputArr[i], hm.get(inputArr[i]) + 1);
            }
            else
            {
                // if the inputArr[i], is found only once
                // put it in the hash map with the frequency of occurrence as 1
                hm.put(inputArr[i] , 1);
            }
            if (idx.containsKey(inputArr[i]) == false) 
            {
                // keeping track of the first occurrence 
                // of the element present in the input array
                idx.put(inputArr[i], i);
            }
        }
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (Map.Entry<Integer , Integer> itr : hm.entrySet()) 
        {
            // the list contains three elements 
            // the first one contains the frequency of the occurrence
            // the second one contains the index of the first occurrence of the element in the input array
            // the third element contains the element whose frequency has been stored as the first element 
            // in the tmp list
            ArrayList<Integer> tmp = new ArrayList<>();
            tmp.add(itr.getValue());
            tmp.add(idx.get(itr.getKey()));
            tmp.add(itr.getKey());
            list.add(tmp);
        }

        // Sorting the values using the custom comparator.
        // instantiating the Comparison class
        Collections.sort(list, new Comparison());

        // Eventually returning the sorted list having the arranged elements.
        ArrayList<Integer> ansList = new ArrayList<>();
        for (int j = 0; j < list.size(); j++) 
        {
            for (int i = 1; i <= list.get(j).get(0); i++) 
            {
                ansList.add(list.get(j).get(2));
            }
        }
        
        int resultArr[] = new int[ansList.size()];
        
        // copying the results in the resultArr
        for(int j = 0 ; j < ansList.size() ; j++)
        {
            resultArr[j] = ansList.get(j);
        }
        return resultArr;
    }
    // main method
    public static void main(String argvs[])
    {
        // input 1
        int inputArr[] = {12, 16, 15, 12, 12, 18, 15, 18, 16, 18, 18};        
        // creating an object of the class SortEleByFreq
        SortEleByFreq obj = new SortEleByFreq();
        int resultArr[] = obj.sortByFreq(inputArr);
        int size = resultArr.length;
        System.out.println("The input array is: ");
        for(int i = 0; i < size; i++)
        {
            System.out.print(inputArr[i] + " ");
        }
        System.out.println("\n ");
        System.out.println("After sorting by frequency of occurrences, the array becomes: ");
        for(int i = 0; i < size; i++)
        {
            System.out.print(resultArr[i] + " ");
        }
        System.out.println("\n ");
        // input 2
        int inputArr1[] = {19, 20, 17, 45, 34, 3, 2, 1, 89, 56, 80, 85, 90};
        int resultArr1[] = obj.sortByFreq(inputArr1);
        size = resultArr1.length;
        System.out.println("The input array is: ");
        for(int i = 0; i < size; i++)
        {
            System.out.print(inputArr1[i] + " ");
        }
        System.out.println("\n ");
        System.out.println("After sorting by frequency of occurrences, the array becomes: ");
        for(int i = 0; i < size; i++)
        {
            System.out.print(inputArr1[i] + " ");
        }
        
        System.out.println("\n ");
    }
}

输出

The input array is: 
12 16 15 12 12 18 15 18 16 18 18 
After sorting by frequency of occurrences, the array becomes: 
18 18 18 18 12 12 12 16 16 15 15 
The input array is: 
19 20 17 45 34 3 2 1 89 56 80 85 90 
After sorting by frequency of occurrences, the array becomes: 
19 20 17 45 34 3 2 1 89 56 80 85 90

复杂度分析：由于我们应用了排序，因此程序的 time complexity 为 O(n * log(n))。我们还创建了一个 array list 来存储结果。因此，space complexity 为 O(n)，其中 n 表示输入数组中的总元素数。

下一主题Java 中的 Beautiful Array

Java 中按频率排序元素

方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中按频率排序元素

方法

算法

实施

相关帖子

Duck Number Java

构建 Java 中的搜索引擎

Java SonarQube

Real-Time Example for Serialization in Java

使用 forEach 循环在 Java 中展平数组流

CharsetDecoder detectedCharset() method in Java with Examples

Java 中比较两个 HashMap

Java 中的索引映射（或允许负数的平凡哈希）

ArrayList vs HashMap

如何在 Java 中从当前日期计算周数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器