请从geeksforgeeks https://www.geeksforgeeks.org/how-to-sort-a-big-array-with-many-repetitions/查看此问题的解决方案2.它使用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;
}
}
这只是std::unordered_map
的一个错字,其操作平均为O(1)。