通过增加频率Leetcode解决方案对数组进行排序  


难度级别 易得奖学金
经常问 易趣 Twilio
算法 排列 编码 哈希图 访谈 面试准备 力码 力码解决方案 排序

问题陈述  

给定整数nums数组,请根据值的频率按升序对数组进行排序。 如果多个值具有相同的频率,请按降序对其进行排序。

使用案列

nums = [1,1,2,2,2,3]
[3,1,1,2,2,2]

说明:

'3'的频率为1,'1'的频率为2,'2'的频率为3。

nums = [2,3,1,3,2]
[1,3,3,2,2]

说明:

'2'和'3'的频率均为2,因此按降序排序。

途径  

在这个问题中,首先我们必须计算每个元素的频率。 为此,我们可以使用 哈希图 在Java中或在C ++中无序设置。 现在我们希望我们的结果数组首先包含那些具有高频率的元素。
为此,我们现在可以根据已经存储在映射中的总输入频率对给定的输入数组进行排序。

现在我们只需要在函数之外创建一个比较器。 在这里,我们将比较两个元素(假设a和b),我们知道每个元素的频率。 因此,如果a的频率大于b,则在数组中将b置于a之前。 下一种情况是,如果a和b的频率相同,则将具有较高值的​​那个元素放在第一位。 例子:

参见
执行字符串移位Leetcode

案例1通过增加频率Leetcode解决方案对数组进行排序Pin

案例2通过增加频率Leetcode解决方案对数组进行排序Pin

算法

  • 创建一个哈希图。
  • 运行一个循环,并为每个元素将map中该元素的计数增加1。
  • 现在创建一个比较器函数,使用存储在映射中的计数比较两个整数。 比较两个元素并确定它们的顺序,如上所述。
  • 使用此比较器对给定的数组进行排序。
  • 返回排序后的数组。

实施   

通过增加频率Leetcode解决方案的用于排序数组的C ++程序

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.second == p2.second) return p1.first > p2.first;
    return p1.second < p2.second;
}

vector<int> frequencySort(vector<int>& nums) 
{
    unordered_map<int,int> m;
    for(auto x:nums) m[x]++;

    vector<pair<int,int> > v;

    for(auto p:m) v.push_back(p);

    sort(v.begin(),v.end(), comp);

    vector<int> res;
    for(auto p:v)
    {
        while(p.second--)
            res.push_back(p.first);
    }

    return res;        
}

int main() 
{
    vector<int> nums = {2,3,1,3,2};
    for(int x: frequencySort (nums))
        cout<<x<<" ";
    return 0; 
}
1 3 3 2 2

通过增加频率Leetcode解决方案来排序数组的Java程序

import java.util.*;
import java.lang.*;

class Comp implements Comparator<Integer>{
    Map<Integer,Integer>map=Rextester.map;
    public int compare(Integer a,Integer b){
        if(map.get(a)>map.get(b))return 1;
        else if(map.get(b)>map.get(a))return -1;
        else{
            if(a>b)return -1;
            else if(a<b)return 1;
            return 0;
        }
    }
}
class Rextester
{  
    static Map<Integer,Integer>map;
    public static int[] frequencySort(int[] nums)
    {
        map=new HashMap<Integer,Integer>();
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i,1+map.get(i));
            }else{
                map.put(i,1);
            }
        }
        Integer[]arr=new Integer[nums.length];
        int k=0;
        for(int i:nums){
            arr[k++]=i;
        }
        Arrays.sort(arr,new Comp());
        k=0;
        for(int i:arr){
            nums[k++]=i;
        }
        return nums;
    }
    
    public static void main(String args[])
    {
        int[]nums={1,1,2,2,2,3};
        nums=frequencySort(nums);
        for(int i:nums)
        {
            System.out.print(i+" ");
        }
    }
}
1 3 3 2 2

通过增加频率Leetcode解决方案对排序数组进行复杂度分析  

时间复杂度

O(nlog(n)): 其中n是输入数组的大小。 哈希映射中的插入和访问花费n个元素的O(n)时间,排序花费nlogn的时间。 因此,时间复杂度将为nlogn。

参见
添加和搜索Word-数据结构设计LeetCode

空间复杂度 

上) : 最糟糕的是,它们可以是数组中的n个不同元素。 因此,地图的大小将为O(n)。

1