Блог

Главная - Вопросы по программированию - Как напечатать элементы в порядке убывания частоты каждого элемента?

Как напечатать элементы в порядке убывания частоты каждого элемента?

#data-structures

Вопрос:

Вам предоставляется массив из N элементов (может не отличаться). Проверьте частоту каждого элемента и выведите элементы в порядке убывания частоты каждого элемента. Если два элемента имеют одинаковую частоту, то сначала будет выведено большее значение.

например:-

N=5 ar[] = {1,2,2,1,6}

Частота элементов :-
1 — 2 раза 2 — 2 раза 6 — 1 раз

Теперь печатайте элементы в порядке убывания частоты. Следовательно, вывод :- {2,1,6}, так как 2 больше 1 и оба имеют одинаковую частоту, поэтому сначала выводится большее значение, т. е. 2.

Я не понимаю логики оптимизации проблемы. Пожалуйста, помогите

Комментарии:

1. Что вы пробовали до сих пор? С какой частью у вас проблемы? Определение частот? Получение массива результатов? Сортировка результирующего массива по частоте?

2. Сохраните частоту с помощью карты (C STL), затем пройдите по карте и скопируйте ее в вектор пар, а затем отсортируйте вектор с помощью пользовательского компаратора.

3. @risingStark по вашим словам, я завершил копирование в векторы пар, но после этого, когда я отсортирую вектор, если я отсортирую его по частоте в порядке убывания, то ответ будет 1,2,6, что не требуется. Мне нужен ответ как 2,1,6

4. @abhishek kaushik Вам нужно использовать функцию сортировки с измененной функцией сравнения, чтобы в случае равной частоты она возвращала большее число. Пример: sort(v.begin(),v.end(),[](const pair<int,int> a, const pair<int,int>b) { if(a.second == b.second) { return a.first > b.first;}else { return a.second > b.second; }});

Ответ №1:

Поскольку вы сортируете вектор в порядке убывания частоты, я предполагаю, что вы пропустили условие равной частоты. Очевидно, что нормальная сортировка сохранит естественный порядок повторяющихся элементов в частотном векторе/списке.

Вам необходимо сначала проверить равенство двух частот. Если равны, то сортируйте по их ключам.

Пример : frequency list={3(2),3(1),3(5),1(9)} Тогда естественная сортировка по убыванию будет : {2,1,5,9} (или {1,2,5,9} в зависимости от реализации). Но вы требуете {5,2,1,9} . Поэтому мы изменим функцию сортировки, как показано ниже :

 sort(v.begin(),v.end(),[](const pair<int,int> a, const pair<int,int>b) { 
    if (a.second == b.second) { 
        return a.first > b.first;
    }else{
        return a.second > b.second; 
    }
});
Метки: