c - 如何按频率找到元素的完整排序？

Question

问题是这样的:

给定一个整数数组，根据元素出现的频率对数组进行排序。例如，如果输入数组为{2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}，则将数组修改为{3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}。如果两个数字具有相同的频率，则打印第一个出现的数字。

我知道如何部分地做到这一点。这是我的方法。

我将创建一个结构，如下所示:

typedef struct node
{
  int index; // for storing the position of the number in the array.
  int count; // for storing the number of times the number appears
  int value; // for storing the actual value
} a[50];

我将创建这些结构的数组，然后根据它们的计数通过排序算法对其进行排序。但是，如何确保如果两个元素的频率相同，那么应该出现索引值较小的数字？

Answer 1

#include <stdlib.h> // qsort, malloc, free
#include <stddef.h> // size_t
#include <stdio.h>  // printf

struct number
{
    const int * value;
    int         num_occurrences;
};

static void cmp_by_val(const struct number * a, const struct number * b)
{
    if (*a->value < *b->value)
        return -1;
    else if (*b->value < *a->value)
        return 1;
    else
        return 0;
}

static void cmp_by_occurrence_stable(const struct number * a, const struct number * b)
{
    if (a->num_occurrences < b->num_occurrences)
        return -1;
    else if (b->num_occurrences < a->num_occurrences)
        return 1;
    else if (a->value < b->value)
        return -1;
    else if (b->value < a->value)
        return 1;
    else
        return 0;
}

static struct number * sort_by_occurrence(const int * arr, size_t N)
{
    //
    // STEP 1: Convert the input
    //
    struct number * sort_arr = (struct number *)malloc(N * sizeof(struct number));
    if (! sort_arr) return NULL;
    for (int k = 0; k < N; ++k)
    {
        sort_arr[k].value = &arr[k];
        sort_arr[k].num_occurrences = 0;
    }
    //
    // STEP 2: Sort the input based on value
    //
    qsort(sort_arr, N, sizeof(struct number), cmp_by_val);
    //
    // STEP 3: Count occurrences
    //
    if (0 < N)
    {
        int cur_value = *sort_arr[0].value;
        int i = 0;
        for (j = 1; j < N; ++j)
        {
            if (*sort_arr[j].value != *sort_arr[i].value)
            {
                for (int k = i; k < j; ++k)
                    sort_arr[k].num_occurrences = j - i;
                i = j;
            }
        }
        for (; i < N; ++i)
            sort_arr[i].num_occurrences = N - i;
    }
    //
    // STEP 4: Sort based on occurrence count
    //
    qsort(sort_arr, N, sizeof(struct number), cmp_by_occurrence_stable);
    //
    // DONE
    //
    return sort_arr;
}

static void print_arr(const struct number * arr, size_t N)
{
    if (0 < N)
    {
        printf("%d", arr[0]->value);
        for (int k = 1; k < N; ++k)
            printf(", %d", arr[k]->value);
    }
    printf("\n");
}

int main(int argc, char ** argv)
{
    const int EXAMPLE_INPUT[11] = { 2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12 }; 
    struct number * sort_arr = sort_by_occurrence(EXAMPLE_INPUT, 11);
    if (sort_arr)
    {
        print_arr(sort_arr, 11);
        free(sort_arr);
    }
};