每日一题：比较字符串最小字母出现频次

题目链接：https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/

# hash 计数 + 二分查找

	class Solution {
	public int[] numSmallerByFrequency(String[] queries, String[] words) {
	int n = words.length;
	int[] arr = new int[n];

	for (int i = 0; i < n; ++i) {
	arr[i] = calcFrequency(words[i]);
	}

	Arrays.sort(arr);

	n = queries.length;
	int[] ret = new int[n];
	for (int i = 0; i < n; ++i) {
	ret[i] = binarySearch(arr, calcFrequency(queries[i]));
	}

	return ret;
	}

	private int binarySearch(int[] arr, int tar) {
	// 二分找第一个大于 tar 的下标
	int l = 0, r = arr.length;
	while (l < r) {
	int m = (l + r) / 2;
	if (arr[m] <= tar) l = m + 1;
	else r = m;
	}
	//arr [l, arr.length - 1] 都是大于 tar 的数
	return arr.length - l;
	}

	private int calcFrequency(String s) {
	int minCnt = 0;
	int minChar = 'z';

	for (char c : s.toCharArray()) {
	if (c < minChar) {
	minCnt = 1;
	minChar = c;
	} else if (c == minChar) {
	++minCnt;
	}
	}

	return minCnt;
	}
	}

	class Solution {
	public int[] numSmallerByFrequency(String[] queries, String[] words) {
	int[] lenMap = new int[12];

	for (String w : words) ++lenMap[calcFrequency(w)];

	// 计算后缀和
	for (int i = 9; i > 0; --i) lenMap[i] += lenMap[i + 1];

	int n = queries.length;
	int[] ret = new int[n];
	for (int i = 0; i < n; ++i) {
	int f = calcFrequency(queries[i]);
	ret[i] = lenMap[f + 1];
	}

	return ret;
	}
	private int calcFrequency(String s) {
	int minCnt = 0;
	int minChar = 'z';

	for (char c : s.toCharArray()) {
	if (c < minChar) {
	minCnt = 1;
	minChar = c;
	} else if (c == minChar) {
	++minCnt;
	}
	}

	return minCnt;
	}
	}