Question

1772. 按受欢迎程度排列功能

English Version

题目描述

给定一个字符串数组 features ，其中 features[i] 是一个单词，描述你最近参与开发的项目中一个功能的名称。你调查了用户喜欢哪些功能。另给定一个字符串数组 responses，其中 responses[i] 是一个包含以空格分隔的一系列单词的字符串。

你想要按照受欢迎程度排列这些功能。 严格地说，令 appearances(word) 是满足 responses[i] 中包含单词 word 的 i 的个数，则当 appearances(features[x]) > appearances(features[y]) 时，第 x 个功能比第 y 个功能更受欢迎。

返回一个数组 sortedFeatures ，包含按受欢迎程度排列的功能名称。当第 x  个功能和第 y 个功能的受欢迎程度相同且 x < y 时，你应当将第 x 个功能放在第 y 个功能之前。

 

示例 1：

输入：features = ["cooler","lock","touch"], responses = ["i like cooler cooler","lock touch cool","locker like touch"]
输出：["touch","cooler","lock"]
解释：appearances("cooler") = 1，appearances("lock") = 1，appearances("touch") = 2。由于 "cooler" 和 "lock" 都出现了 1 次，且 "cooler" 在原数组的前面，所以 "cooler" 也应该在结果数组的前面。

示例 2：

输入：features = ["a","aa","b","c"], responses = ["a","a aa","a a a a a","b a"]
输出：["a","aa","b","c"]

 

提示：

• 1 <= features.length <= 104
• 1 <= features[i].length <= 10
• features 不包含重复项。
• features[i] 由小写字母构成。
• 1 <= responses.length <= 102
• 1 <= responses[i].length <= 103
• responses[i] 由小写字母和空格组成。
• responses[i] 不包含两个连续的空格。
• responses[i] 没有前置或后置空格。

解法

方法一：哈希表 + 自定义排序

我们遍历 responses，对于 responses[i] 中的每个单词，我们用一个哈希表 vis 暂存。接下来将 vis 中的单词记录到哈希表 cnt 中，记录每个单词出现的次数。

接下来，采用自定义排序，将 features 中的单词按照出现次数从大到小排序，如果出现次数相同，则按照出现的下标从小到大排序。

时间复杂度 $O(n \times \log n)$，其中 $n$ 为 features 的长度。

class Solution:
  def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
    cnt = Counter()
    for s in responses:
      for w in set(s.split()):
        cnt[w] += 1
    return sorted(features, key=lambda w: -cnt[w])

class Solution {
  public String[] sortFeatures(String[] features, String[] responses) {
    Map<String, Integer> cnt = new HashMap<>();
    for (String s : responses) {
      Set<String> vis = new HashSet<>();
      for (String w : s.split(" ")) {
        if (vis.add(w)) {
          cnt.merge(w, 1, Integer::sum);
        }
      }
    }
    int n = features.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) {
      idx[i] = i;
    }
    Arrays.sort(idx, (i, j) -> {
      int x = cnt.getOrDefault(features[i], 0);
      int y = cnt.getOrDefault(features[j], 0);
      return x == y ? i - j : y - x;
    });
    String[] ans = new String[n];
    for (int i = 0; i < n; i++) {
      ans[i] = features[idx[i]];
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> sortFeatures(vector<string>& features, vector<string>& responses) {
    unordered_map<string, int> cnt;
    for (auto& s : responses) {
      istringstream iss(s);
      string w;
      unordered_set<string> st;
      while (iss >> w) {
        st.insert(w);
      }
      for (auto& w : st) {
        ++cnt[w];
      }
    }
    int n = features.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
      int x = cnt[features[i]], y = cnt[features[j]];
      return x == y ? i < j : x > y;
    });
    vector<string> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = features[idx[i]];
    }
    return ans;
  }
};

func sortFeatures(features []string, responses []string) []string {
  cnt := map[string]int{}
  for _, s := range responses {
    vis := map[string]bool{}
    for _, w := range strings.Split(s, " ") {
      if !vis[w] {
        cnt[w]++
        vis[w] = true
      }
    }
  }
  sort.SliceStable(features, func(i, j int) bool { return cnt[features[i]] > cnt[features[j]] })
  return features
}

function sortFeatures(features: string[], responses: string[]): string[] {
  const cnt: Map<string, number> = new Map();
  for (const s of responses) {
    const vis: Set<string> = new Set();
    for (const w of s.split(' ')) {
      if (vis.has(w)) {
        continue;
      }
      vis.add(w);
      cnt.set(w, (cnt.get(w) || 0) + 1);
    }
  }
  const n = features.length;
  const idx: number[] = Array.from({ length: n }, (_, i) => i);
  idx.sort((i, j) => {
    const x = cnt.get(features[i]) || 0;
    const y = cnt.get(features[j]) || 0;
    return x === y ? i - j : y - x;
  });
  return idx.map(i => features[i]);
}