1772.md

1772. 按受欢迎程度排列功能 （1772. Sort Features by Popularity）

解题思路

定制化排序函数即可，需要提前建立两个map，一个map用来保存feature 到其index的映射，以便频率相同时，按照下标升序排列。另外一个map，保存feature到其出现频率的映射。注意这里需要用set将同一个调查反馈中的feature唯一化一下，因为同一个调查问卷中出现一个feature多次只能算一次，用set再合适不过。具体实现C++/Java/Python都差不多，仅仅是语法的区别。大家根据偏好，从下面的tab里选择自己喜欢的版本看就好。

代码

class Solution {
public:
    vector<string> sortFeatures(vector<string>& features, vector<string>& responses) {
        unordered_map<string, int> feature2Idx;
        unordered_map<string, int> feature2Freq;
        for (int i = 0; i < features.size(); i++) {
            feature2Idx[features[i]] = i;
        }
        for (const auto& r : responses) {
            stringstream ss(r);
            unordered_set<string> featureSet; // to unique freature in currrent reponse
            string feature;
            while (ss >> feature) {
                featureSet.insert(feature);
            }
            for (const auto& fs : featureSet) {
                feature2Freq[fs]++;
            }
        }

        auto cmp = [&](const auto& str1, const auto& str2) {
            return feature2Freq[str1] > feature2Freq[str2] ||
                (feature2Freq[str1] == feature2Freq[str2] && feature2Idx[str1] < feature2Idx[str2]);
        };
        sort(features.begin(), features.end(), cmp);
        return features;
    }
};

import java.util.Map.Entry;

class Solution {
    public String[] sortFeatures(String[] features, String[] responses) {
        Map<String, Integer> featureFreq = new HashMap<>();
        Map<String, Integer> featureIdx = new HashMap<>();
        int i = 0;
        for (String feature : features) {
            featureFreq.put(feature, 0); // initialize all feature freq to 0
            featureIdx.put(feature, i++);
        }

        Set<String> set = new HashSet<>();
        i = 0;
        for (String response : responses) {
            String[] arr = response.split(" "); // response feature array
            for (String a : arr) {
                if (featureFreq.get(a) != null && !set.contains(a)) {
                    featureFreq.put(a, featureFreq.get(a) + 1);
                    set.add(a);
                }
            }
            set.clear();
        }

        List<Entry<String, Integer>> list = new ArrayList(featureFreq.entrySet());
        Collections.sort(list, (e1, e2)->{
            if(e1.getValue() != e2.getValue()) return e2.getValue() - e1.getValue();
            else return featureIdx.get(e1.getKey()) - featureIdx.get(e2.getKey());
        });

        String[] res = new String[features.length];
        for (i = 0; i < list.size(); i++) {
            res[i] = list.get(i).getKey();
        }

        return res;
    }
}

class Solution(object):
    def sortFeatures(self, features, responses):
        featureSet = set(features)
        order = {word : i for i, word in enumerate(features)}
        freq = collections.defaultdict(int)
        for r in responses:
            for word in set(r.split(' ')):
                if word in featureSet:
                    freq[word] += 1
        features.sort(key = lambda x : (-freq[x], order[x]))

        return features

点我赞赏作者

github 题解