c++ - 通过增加元素的频率对数组进行排序

Question

我想按频率递增的顺序对数组进行排序。例如，如果我有一个数组

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

或另一个数组将包含以下序列:

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

但是，我不能使用散列或映射——我只能使用数组。我想到的是使用快速排序算法对数组进行排序，扫描排序后的数组并在二维数组中执行计数，以便对于每个元素，都有一个与之关联的计数，然后按计数排序。如果两个计数相同，那么我只会先打印出具有较低值的那个。我在执行最后两个步骤时遇到问题。我不确定如何将计数“映射”到二维数组中的索引，也不确定如何按计数对二维数组进行排序。谁能帮帮我？谢谢!

Answer 1

扫描您的数组(先排序以优化，但不需要)，并生成以下结构的数组。现在对这些结构的数组进行排序，然后重新生成原始数组。

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

        return Elem<other.Elem;
    }
};