通过增加元素的频率对数组排序 [英] 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};

但是，我不能使用哈希或地图–我只能使用数组。我想到的是使用快速排序算法排序数组，扫描排序的数组并在2d数组中执行计数，因此对于每个元素，有一个计数相关联，然后按计数排序。如果两个计数相同，那么我只打印出一个较低的值首先。我无法实施最后两个步骤。我不知道如何映射计数到2d数组中的索引，也不知道如何通过计数排序2d数组。有谁能帮助我吗？谢谢！

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!

推荐答案

这就是我没有STL的代码（需要额外的O

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屋！