Сортировка массива по возрастанию частоты Решение Leetcode  


Сложный уровень Легко
Часто спрашивают в eBay Twilio
алгоритмы массив кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Сортировка

Постановка задачи  

Учитывая массив целых чисел 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 одинакова, тогда сначала поместите тот элемент, который имеет более высокое значение. Пример:

Дело 1Сортировка массива по возрастанию частоты Решение Leetcode

Смотрите также
Выполнить сдвиг строки Leetcode

Дело 2Сортировка массива по возрастанию частоты Решение Leetcode

Алгоритм

  • Создайте хеш-карту.
  • Запустите цикл и для каждого элемента увеличьте счетчик этого элемента на карте на 1.
  • Теперь создайте функцию компаратора для сравнения двух целых чисел, используя их счетчик, хранящийся в карте. Сравните два элемента и определите их порядок, как описано выше.
  • Отсортируйте данный массив с помощью этого компаратора.
  • Верните отсортированный массив.

Реализация  

Программа C ++ для сортировки массива путем увеличения частоты Решение Leetcode

#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

Программа Java для сортировки массива путем увеличения частоты Решение Leetcode

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 - размер входного массива. Вставка и доступ в хеш-карту занимает O (n) времени для n элементов, а сортировка занимает nlogn времени. Следовательно, временная сложность будет nlogn.

Космическая сложность 

На) : В худшем случае это может быть n различных элементов в массиве. Таким образом, размер карты будет O (n).

Смотрите также
Добавление и поиск слова - разработка структуры данных LeetCode