Question

1772. Sort Features by Popularity

中文文档

Description

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.

Solutions

Solution 1: Hash Table + Custom Sorting

We traverse responses, and for each word in responses[i], we temporarily store it in a hash table vis. Next, we record the words in vis into the hash table cnt, recording the number of times each word appears.

Next, we use custom sorting to sort the words in features in descending order of occurrence. If the number of occurrences is the same, we sort them in ascending order of the index where they appear.

The time complexity is $O(n \times \log n)$, where $n$ is the length of 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]);
}