如何找到按频率完整排序的元素? [英] how to find complete sorting of elements by frequency?

问题描述

问题出在这里

给出一个整数数组，根据元素的频率对该数组进行排序.例如，如果输入数组为{2，3，2，4，5，12，12，2，3，3，3，12}，则将数组修改为{3，3，3，3，2，2，2、12、12、4、5}.如果2个数字的频率相同，则打印第1个数字.

Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}. if 2 numbers have same frequency then print the one which came 1st.

我知道该怎么做.这是我的方法.

I know how to do it partially. Here is my approcach.

我将创建一个类似于以下内容的结构:

I will create a struct which will be like:

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];

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

I will create an array of these structs, I will then sort it by a sorting algorithm on the basis of their count. However, how can I ensure that if the frequency of two elements are same, then that number should appear which has a lesser index value?

推荐答案

#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);
    }
};

这篇关于如何找到按频率完整排序的元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！