Сортировать элементы массива по частоте
Просто добавьте что-то примечательное здесь.
myQueue.hpp:
template <class T>
class QueueA {
int size;
...
public:
template <class T> T dequeue() {
// implementation here
}
bool isEmpty();
...
}
myQueue можно определить методы шаблонного класса, которые просто прекрасны в файле реализации. cpp:
// implementation of regular methods goes like this:
template <class T> bool QueueA<T>::isEmpty() {
return this->size == 0;
}
main()
{
QueueA<char> Q;
...
}
4 ответа
Не существует способа сортировки с O (n) сложностью по времени. Посмотрите на сложность наихудшего случая для популярных алгоритмов в Википедии.
Лучшая временная сложность в худшем случае - O (nlogn). Вот как мы можем решить это за O (nlogn) сложность времени:
let array = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
extension Array where Element: Comparable & Hashable {
func countableSorted() -> [Element] {
var counts = [Element: Int]()
// O(n)
for element in self {
counts[element] = (counts[element] ?? 0) + 1
}
// I think that standart method uses O(nlogn) time complexity.
// O(nlogn) + O(n) approximately equal to O(nlogn).
let sorted = counts.sorted { item1, item2 -> Bool in
if item2.value > item1.value {
return true
}
if item2.value == item1.value {
return item2.key > item1.key
}
return false
}
var result = [Element]()
// O(n)
for item in sorted {
let items = Array(repeating: item.key, count: item.value)
result.append(contentsOf: items)
}
// Total time complexity for worst case scenario is O(nlogn)
return result
}
}
print(array.countableSorted())
// Output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]
Я хочу добавить решение в O (n)
Сортировка требует O (nLogn), но этот вопрос также можно решить без использования сортировки с помощью HashMap в Java, потому что [ 1114] содержит пары, отсортированные по ключу.
import java.util.*;
class Simple
{
public static void main(String[] arg)
{ int inputArray[] = {1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2};
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
Map<Integer,List<Integer>> map2 = new HashMap<Integer,List<Integer>>();
for(int i: inputArray)
{
if(map.get(i) == null){
map.put(i, 1) ;
}
else{
int a = map.get(i);
map.put(i,a+1);
}
}
// using for-each loop for iteration over Map.entrySet()
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
if(map2.get(entry.getValue()) == null){
map2.put(entry.getValue(), new ArrayList<Integer>()) ;
}
map2.get(entry.getValue()).add(entry.getKey());
}
for(Map.Entry<Integer,List<Integer>> entry : map2.entrySet()){
for(int j=0; j<entry.getValue().size(); j++){
for(int i=0; i<entry.getKey(); i++){
System.out.print(entry.getValue().get(j) + " ");
}
}
}
}
}
- В цикле First for я перебираю массив, сохраняющий пару (value, Occurrence) в map1 (HashMap). Это займет O (n), так как операция вставки HashMap (вставка) принимает O (1).
- Во втором цикле я перебираю map1 и вставляю пару из (вхождение, список чисел в данном массиве с этим вхождением) в map2 (HashMap2).
- Теперь в последнем цикле for я перебираю map2 и печатаю все списки один за другим, это означает, что я печатаю каждый элемент данного массива один раз, т.е. я перебираю список каждого ключа и печатаю каждый элемент списка [ 1116] клавиша количество раз. Так что это также займет O (n).
Подробнее о HashMap Сложность времени: O (n)
Swift Версия вышеуказанного кода
[111 ]}
Сложность времени в Swift O (nLogn)
Вы можете попробовать приведенный ниже код, это сработало правильно.
var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
inputArray.sort()
let freq = inputArray.sorted { f, s in
inputArray.filter { [110] == f}.count < inputArray.filter { [110] == s}.count
}
print(freq)
Не уверен насчет сложности времени.
Я думаю, что этот вид сортировки может быть достигнут в O (n), с чем-то вроде следующего:
let input = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
// build the frequency dictionary (easy task)
let frequencies = input.reduce(into: [:]) { [110][$1] = ([110][$1] ?? 0) + 1 }
// allocate a 2-D array of ints, each item in this array will hold the numbers that
// appear I times in the input array
let frequencyTable: [[Int]] = frequencies.reduce(into: Array(repeating: [Int](), count: input.count)) {
// substracting one as arrays are zero indexed
// we can't get of of bounds here since the maximum frequency is the
// number of elements in the input array
// Also replicating the numbers by their frequency, to have
// the same contents as in the input array
[110][$1.value - 1] += Array(repeating: $1.key, count: $1.value)
}
// lastly, simply flatten the 2-D array to get the output we need
let output = frequencyTable.flatMap { [110] }
print(output)
Пример результата:
[4, 1, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]
Обратите внимание, что порядок числа с одинаковой частотой могут отличаться в зависимости от того, как работает хэш-функция словаря.
Также мы жертвуем пространство (выделенный 2-D массив) в пользу времени.
Содержание frequencyTable будет выглядеть примерно так (опять-таки порядок 1, 4, 3 может отличаться):
[[4, 3, 1], [2, 2], [5, 5, 5], [6, 6, 6, 6], [], [], [], [], [], [], [], []]