题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给两个字符串数组，看一个数组中各个字符串的最小字母频次，在另一个数组所有字符串的最小字母频次中，排第几。

思路分享

  • 分别对两个数组做转换成最小字母频次的整型数组，然后让一个数组的各值在另一个数组做二分查找找到自己的位置即可。

  • 二分的基本思想在 【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

  • 重点注意一个小问题，字典序的顺序与数字不同，字典序中 2 比 10 大，因为 2 大于 10 的第一位 1，所以 2 更大。正因如此，不能在 string 的数组上直接排序。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> q;
        for (string &s : queries) {
            sort(s.begin(), s.end());
            char tar = s[0];
            int index = ranges::upper_bound(s, tar) - s.begin();
            q.push_back(index);
        }

        vector<int> w;
        for (string &s : words) {
            sort(s.begin(), s.end());
            char tar = s[0];
            int index = ranges::upper_bound(s, tar) - s.begin();
            w.push_back(index);
        }

        sort(w.begin(), w.end());

        vector<int> res(q.size());

        for (int i = 0; i < q.size(); i++) {
            res[i] = w.end()-ranges::upper_bound(w, q[i]);
        }

        return res;
    }
};