You are given a string array features
where features[i]
is a single word that represents the name of a feature of the latest product you are working on. You have made a survey where users have reported which features they like. You are given a string array responses
, where each responses[i]
is a string containing space-separated words.
The popularity of a feature is the number of responses[i]
that contain the feature. You want to sort the features in non-increasing order by their popularity. If two features have the same popularity, order them by their original index in features
. Notice that one response could contain the same feature multiple times; this feature is only counted once in its popularity.
Return the features in sorted order.
Example 1:
Input: features = ["cooler","lock","touch"], responses = ["i like cooler cooler","lock touch cool","locker like touch"] Output: ["touch","cooler","lock"] Explanation: appearances("cooler") = 1, appearances("lock") = 1, appearances("touch") = 2. Since "cooler" and "lock" both had 1 appearance, "cooler" comes first because "cooler" came first in the features array.
Example 2:
Input: features = ["a","aa","b","c"], responses = ["a","a aa","a a a a a","b a"] Output: ["a","aa","b","c"]
Constraints:
1 <= features.length <= 104
1 <= features[i].length <= 10
features
contains no duplicates.features[i]
consists of lowercase letters.1 <= responses.length <= 102
1 <= responses[i].length <= 103
responses[i]
consists of lowercase letters and spaces.responses[i]
contains no two consecutive spaces.responses[i]
has no leading or trailing spaces.
Companies:
Amazon
Related Topics:
Array, Hash Table, String, Sorting
Similar Questions:
// OJ: https://leetcode.com/problems/sort-features-by-popularity/
// Author: github.com/lzl124631x
// Time: O(R + FlogF)
// Space: O(F)
class Solution {
public:
vector<string> sortFeatures(vector<string>& F, vector<string>& R) {
unordered_map<string, int> m, index;
for (int i = 0; i < F.size(); ++i) index[F[i]] = i;
for (auto &r : R) {
stringstream ss(r);
string word;
unordered_set<string> seen;
while (ss >> word) {
if (index.count(word)) seen.insert(word);
}
for (auto &s : seen) m[s]++;
}
sort(begin(F), end(F), [&](auto &a, auto &b) { return m[a] != m[b] ? m[a] > m[b] : index[a] < index[b]; });
return F;
}
};
// OJ: https://leetcode.com/problems/sort-features-by-popularity/
// Author: github.com/lzl124631x
// Time: O(R + FlogF)
// Space: O(F)
class Solution {
public:
vector<string> sortFeatures(vector<string>& F, vector<string>& R) {
unordered_map<string, int> m;
for (int i = 0; i < F.size(); ++i) m[F[i]] = 0;
for (auto &r : R) {
stringstream ss(r);
string word;
unordered_set<string> seen;
while (ss >> word) {
if (m.count(word)) seen.insert(word);
}
for (auto &s : seen) m[s]++;
}
map<int, vector<string>, greater<>> rank;
for (auto &f : F) rank[m[f]].push_back(f);
vector<string> ans;
for (auto &[r, fs] : rank) {
for (auto &f : fs) ans.push_back(f);
}
return ans;
}
};