通过元件的频率增加对数组排序 [英] Sorting an array by increasing frequency of element
问题描述
我想一个数组增加订单的频率进行排序。举例来说,如果我有一个数组
I would like to sort an array by increasing order of frequency. For example, if I had an array
int arr[] = { 3, 3, 10, 2, 5, 10, 10, 2, 2, 2 };
或另一个阵列将具有如下序列在它
or another array would have the following sequence in it:
int arr[] = {5, 3, 3, 10, 10, 10, 2, 2, 2, 2};
不过,我不能使用散列或地图&ndash的;我只能用数组。我所想到的是利用一个快速排序算法的排序阵列,扫描排序后的数组,并在一个二维数组进行计数,从而使各元件,有一个与它相关联的计数,然后通过计数排序。如果两项罪名都一样的话,我只会打印出一个具有较低值第一。我在执行最后两个步骤的麻烦。我不知道如何地图的计数来索引的二维数组中,我也不是一定就如何将二维数组由数排序。任何人都可以帮我吗?谢谢!
However, I cannot use hashing or maps – I can only use arrays. What I have thought of is sorting the array using a quick sort algorithm, scanning the sorted array and performing the count in a 2d array so that for each element, there is a count associated with it, and then sorting by count. If two counts are same then I would merely print out the one with the lower value first. I'm having trouble implementing the last two steps. I'm not sure how to "map" a count to an index in the 2d array, nor am I sure on how to sort the 2d array by a count. Could anyone help me out? Thanks!
推荐答案
这就是我倒是code就没有STL(需要额外的O(n)的内存):
That's how I'd code it without STL (requires additional O(n) memory):
// Represents a bunch of equal numbers in an array
struct Bunch
{
int x; // value of numbers
int n; // count of numbers
};
int cmp_int(const void *x, const void *y)
{
return *static_cast<const int*>(x) - *static_cast<const int*>(y);
}
int cmp_bunch(const void *x, const void *y)
{
const Bunch* bx = static_cast<const Bunch*>(x);
const Bunch* by = static_cast<const Bunch*>(y);
return (bx->n != by->n) ? bx->n - by->n : bx->x - by->x;
}
void sort_by_freq(int arr[], int arr_size)
{
// Buffer array to store counted bunches of numbers
Bunch* buf = new Bunch [arr_size];
int buf_size = 0;
// Sort input array
qsort(arr, arr_size, sizeof(int), cmp_int);
// Compute bunches
Bunch bunch;
bunch.x = arr[0];
bunch.n = 1;
for (int i = 1; i < arr_size; ++i)
{
if (arr[i] > bunch.x)
{
buf[buf_size++] = bunch;
bunch.x = arr[i];
bunch.n = 1;
}
else
{
++bunch.n;
}
}
buf[buf_size++] = bunch; // Don't forget the last one!
// Sort bunches
qsort(buf, buf_size, sizeof(Bunch), cmp_bunch);
// Populate bunches to the input array
int i = 0;
for (int k = 0; k < buf_size; ++k)
for (int j = 0; j < buf[k].n; ++j) arr[i++] = buf[k].x;
// Don't forget to deallocate buffer, since we cannot rely on std::vector...
delete [] buf;
}
这篇关于通过元件的频率增加对数组排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!