时间戳

首页 > 解决方案 > 按 C/C++ 中的出现频率对数组进行排序

arrays - 按 C/C++ 中的出现频率对数组进行排序

问题描述

这里我有两个数组，一个字符串和一个 int：

S[]={"abc","abc","aa","a","aa","abc"}
A[]={  3,    2,   4,   5,  6,   7 }

S[] 中的每个元素都与 A[] 中的相应元素链接（例如：“abc”-3、“abc”-2 等）

我想按 S[i] 的出现频率对这些数组进行排序，例如：

Sorted arrays: S[]={"abc","abc","abc","aa","aa","a"}
               A[]={ 2,    3,    7,    4,   6,   5 }

所以 S[] 按 s[i] 出现的频率排序，如果两个元素的频率相同，字母表中“较小”的元素排在第一位。

如果两个 s[] 元素相同，则对应的 a[] 元素应该递增排序。

我应该用什么来对它们进行排序，配对或使用地图，因为我尝试使用这些但我仍然卡住了。

任何有关示例代码的想法都将不胜感激。

标签： arraysstringsortingfrequency

解决方案

我会分两步完成。首先，我会计算频率（可以使用std::mapor std::unordered_map。然后我会进行排序，使用它作为主键，使用字符串和关联的数字作为二级和三级键。

#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

using T = std::pair<std::string, int>;

namespace std {
std::ostream &operator<<(std::ostream &os, T const &t) {
    return os << t.first << ", " << t.second;
}
}

int main() {

    std::vector<T> inputs {
        { "abc", 3 }, {"abc", 2}, { "aa", 4}, {"a", 5}, { "aa", 6 }, { "abc", 7 }
    };

    std::unordered_map<std::string, int> counts;

    // first count the frequencies:
    for (auto const & i : inputs)
        ++counts[i.first];

    // order by freq desc, first asc, num asc
    std::sort(inputs.begin(), inputs.end(),
        [&](T const& a, T const& b) {
            if (counts[b.first] < counts[a.first])
                return true;
            if (counts[a.first] < counts[b.first])
                return false;
            if (a.first < b.first)
                return true;
            if (b.first < a.first)
                return false;
            return a.second < b.second;
        });

    // Show the result:
    std::copy(inputs.begin(), inputs.end(), std::ostream_iterator<T>(std::cout, "\n"));
}

推荐阅读