4

頻度の昇順で配列をソートしたいと思います。たとえば、配列がある場合

int arr[] = { 3, 3, 10, 2, 5, 10, 10, 2, 2, 2 };

または、別の配列には次のシーケンスが含まれます。

int arr[] = {5, 3, 3, 10, 10, 10, 2, 2, 2, 2};

ただし、ハッシュやマップは使用できません。使用できるのは配列のみです。私が考えたのは、クイックソートアルゴリズムを使用して配列をソートし、ソートされた配列をスキャンし、2次元配列でカウントを実行して、各要素に関連付けられたカウントがあり、次にカウントでソートすることです。2 つのカウントが同じ場合は、値が小さい方を最初に出力するだけです。最後の 2 つの手順の実装に問題があります。カウントを 2 次元配列のインデックスに「マップ」する方法も、2 次元配列をカウントでソートする方法もわかりません。誰か助けてくれませんか？ありがとう！

4

2 に答える 2

4

配列をスキャンし (最初に並べ替えて最適化しますが、必要ありません)、以下の構造体の配列を生成します。これらの構造体の配列を並べ替えてから、元の配列を再生成します。

struct ElemCount {
    int Elem;
    int count;
    bool operator<(const ElemCount& other) {
        if (count!=other.count)
            return count<other.count;

        return Elem<other.Elem;
    }
};
于 2012-11-15T04:52:45.547 に答える
2

それがSTLなしでコーディングする方法です（追加のO（n）メモリが必要です）：

// 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;
}
于 2012-11-15T07:02:59.267 に答える