Использование stl :: map и stl :: unordered_map для сортировки данных массива, который содержит много повторяющихся элементов - PullRequest
Новая
       44

Использование stl :: map и stl :: unordered_map для сортировки данных массива, который содержит много повторяющихся элементов

0 голосов
/ 23 марта 2019

Пожалуйста, посмотрите на решение 2 этого вопроса от geeksforgeeks https://www.geeksforgeeks.org/how-to-sort-a-big-array-with-many-repetitions/ Он использует stl :: map и говорит, что решением является O (n + mlogm), что предполагает, что вставка и поиск stl :: map происходят за O (1). Это правильно?

код в указанной ссылке: 

void sort(int arr[], int n) 
{ 
   //1. Create an empty hash table. 
    map<int, int> count; 

    //2. Input array values are stores as key and their 
    //counts are stored as value in hash table. 
    for (int i=0; i<n; i++) 
        count[arr[i]]++; 

    map<int, int>::iterator it; 
    int index = 0; 

    //3. Consider all keys of hash table and sort them. 
    //In std::map, keys are already sorted. 

    //4. Traverse all sorted keys and print every key its value times. 
    for (it=count.begin(); it!=count.end(); ++it) 
    { 
        while(it->second--) 
        arr[index++]=it->first; 
    } 
}

1 Ответ

0 голосов
/ 24 марта 2019

Это просто опечатка для std::unordered_map, чьи операции в среднем O (1).

...