1170. 比较字符串最小字母出现频次 (opens new window)

1.二分查找

开辟一个数组空间保存词汇表words中每一个单词的函数结果，对数组排序并使用二分查找，找到函数值大于当前单词函数值序列的最左索引。

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] find=new int[words.length];
        int[] res=new int[queries.length];
        for(int i=0;i<words.length;i++){
            char c=words[i].charAt(0);
            int sum=1;
            for(int j=1;j<words[i].length();j++){
                if(words[i].charAt(j)-c>0){
                    continue;
                }
                else if(words[i].charAt(j)-c<0){
                    sum=1;
                    c=words[i].charAt(j);
                }
                else{
                    sum++;
                }
            }
            find[i]=sum;
        }
        //排序，为二分查找做准备
        Arrays.sort(find);
        
        for(int i=0;i<queries.length;i++){
            char c=queries[i].charAt(0);
            int sum=1;
            for(int j=1;j<queries[i].length();j++){
                if(queries[i].charAt(j)-c>0){
                    continue;
                }
                else if(queries[i].charAt(j)-c<0){
                    sum=1;
                    c=queries[i].charAt(j);
                }
                else{
                    sum++;
                }
            }
            //二分查找
            int left=0,right=find.length-1;
            while(left<right){
                int mid=(left+right)/2;
                if(find[mid]>sum)right=mid;
                else left=mid+1;
            }
            res[i]=find[left]<=sum?0:find.length-left;
        }
        return res;
    }
}