D.二分查找-进阶——1170. 比较字符串最小字母出现频次

题目链接：1170. 比较字符串最小字母出现频次（中等）

算法原理：

解法：二分查找-求最右端点

6ms击败44.49%

时间复杂度O(Nlogn)

问题转化：将次数都抽取出来，那么就是说从words的次数数组中找到比queries[i]的次数大的次数的个数

问题转化后跟下面这题基本一模一样👇

D.二分查找-基础——744. 寻找比目标字母大的最小字母

大家如果还是看不懂的话就看下面的笔记吧，从怎么想到的->如何推导的->如何理解，全能解决👇

Java代码：

class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { //问题转化：将次数都抽取出来，那么就是说从words的次数数组中找到比queries[i]的次数大的次数的个数 int n=queries.length,m=words.length; int[] nums1=new int[n]; int[] nums2=new int[m]; for(int i=0;i<n;i++) nums1[i]=f(queries[i]); for(int i=0;i<m;i++) nums2[i]=f(words[i]); Arrays.sort(nums2); int[] ret=new int[n]; for(int i=0;i<n;i++){ //设定目标值t int t=nums1[i]; //找最右端点 int left=0,right=m-1; while(left<right){ int mid=left+(right-left+1)/2; if(nums2[mid]>t) right=mid-1; else left=mid; } ret[i]=nums2[left]>t?m:(left+1<m?m-(left+1):0); } return ret; } //计算每个字符串的字数 private int f(String s){ //只有小写字母，可用数组代替哈希表 int[] hash=new int[26]; //记录出现的最小的字母的索引 int min=26; for(char c:s.toCharArray()){ int index=c-'a'; hash[index]++; min=index<min?index:min; } return hash[min]; } }