题目描述
定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。 例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。 现在，给你两个字符串数组待查表 queries 和词汇表 words 。 对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。 请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。 示例 1： 输入：queries = ["cbd"], words = ["zaaaz"] 输出：[1] 解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。 示例 2： 输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] 输出：[1,2] 解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。 提示： 1 <= queries.length <= 2000 1 <= words.length <= 2000 1 <= queries[i].length, words[i].length <= 10 queries[i][j]、words[i][j] 都由小写英文字母组成。
思路及实现
方式一
思路
首先，我们需要统计两个字符串中每个字符出现的频次。然后，我们找到两个频次映射中最小的频次。最后，比较这两个最小频次，返回其中较小的一个。如果两个字符串中有不同的字符，则返回-1。
代码实现
Java版本
import java.util.HashMap; import java.util.Map; public class Solution { public int minFreq(String s1, String s2) { // 统计s1中每个字符出现的频次 Map<Character, Integer> freq1 = countFreq(s1); // 统计s2中每个字符出现的频次 Map<Character, Integer> freq2 = countFreq(s2); // 检查两个字符串是否有不同的字符 if (!freq1.keySet().containsAll(freq2.keySet()) || !freq2.keySet().containsAll(freq1.keySet())) { return -1; } int minFreq1 = Integer.MAX_VALUE; int minFreq2 = Integer.MAX_VALUE; // 找到两个频次映射中的最小频次 for (int freq : freq1.values()) { minFreq1 = Math.min(minFreq1, freq); } for (int freq : freq2.values()) { minFreq2 = Math.min(minFreq2, freq); } // 返回较小的最小频次 return Math.min(minFreq1, minFreq2); } private Map<Character, Integer> countFreq(String s) { Map<Character, Integer> freq = new HashMap<>(); for (char c : s.toCharArray()) { freq.put(c, freq.getOrDefault(c, 0) + 1); } return freq; } }
说明：
countFreq方法用于统计字符串中每个字符出现的频次。- 在
minFreq方法中，我们首先检查两个字符串是否有不同的字符，如果有，则返回-1。- 然后，我们遍历两个频次映射，找到各自的最小频次。
- 最后，返回两个最小频次中的较小值。
C语言版本
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define MAX_CHAR 256 int minFreq(char *s1, char *s2) { int freq1[MAX_CHAR] = {0}; int freq2[MAX_CHAR] = {0}; int minFreq1 = INT_MAX; int minFreq2 = INT_MAX; int hasDiffChar = 0; // 统计s1中每个字符出现的频次 for (int i = 0; s1[i]; i++) { freq1[s1[i]]++; } // 统计s2中每个字符出现的频次 for (int i = 0; s2[i]; i++) { freq2[s2[i]]++; if (freq1[s2[i]] == 0) { hasDiffChar = 1; } } // 如果s1和s2有不同的字符，返回-1 if (hasDiffChar) { return -1; } // 找到两个频次数组中的最小频次 for (int i = 0; i < MAX_CHAR; i++) { if (freq1[i] != 0) { minFreq1 = (minFreq1 > freq1[i]) ? freq1[i] : minFreq1; } if (freq2[i] != 0) { minFreq2 = (minFreq2 > freq2[i]) ? freq2[i] : minFreq2; } } // 返回较小的最小频次 return (minFreq1 < minFreq2) ? minFreq1 : minFreq2; } int main() { char s1[] = "abcc"; char s2[] = "aabb"; printf("The minimum frequency of the smallest character is: %d\n", minFreq(s1, s2)); return 0; }
说明：
- 使用两个数组
freq1和freq2来存储两个字符串中每个字符出现的频次。- 在统计
s2的频次时，检查s1是否包含s2中的每个字符。- 遍历两个频次数组，找到各自的最小频次。
- 返回较小的最小频次。
Python3版本
from collections import Counter def minFreq(s1: str, s2: str) -> int: # 统计s1和s2中每个字符出现的频次 freq1 = Counter(s1) freq2 = Counter(s2) # 检查两个字符串是否有不同的字符 if not freq1.keys() == freq2.keys(): return -1 # 找到两个频次映射中的最小频次 min_freq1 = min(freq1.values()) min_freq2 = min(freq2.values()) # 返回较小的最小频次 return min(min_freq1, min_freq2) # 示例 s1 = "abcc" s2 = "aaabbbcc" result = minFreq(s1, s2) print(f"The minimum frequency of the smallest character is: {result}")
说明：
- 使用Python的
collections.Counter来统计字符频次。- 检查两个字符串的字符集合是否相同。
- 找到并返回最小的频次。
Golang版本
package main import ( "fmt" ) func minFreq(s1, s2 string) int { freq1 := make(map[rune]int) freq2 := make(map[rune]int) minFreq1 := int(^uint(0) >> 1) minFreq2 := int(^uint(0) >> 1) hasDiffChar := false // 统计s1中每个字符出现的频次 for _, ch := range s1 { freq1[ch]++ } // 统计s2中每个字符出现的频次 for _, ch := range s2 { freq2[ch]++ if _, ok := freq1[ch]; !ok { hasDiffChar = true } } // 如果s1和s2有不同的字符，返回-1 if hasDiffChar { return -1 } // 找到两个频次映射中的最小频次 for _, freq := range freq1 { if freq < minFreq1 { minFreq1 = freq } } for _, freq := range freq2 { if freq < minFreq2 { minFreq2 = freq } } // 返回较小的最小频次 if minFreq1 < minFreq2 { return minFreq1 } return minFreq2 } func main() { s1 := "abcc" s2 := "aaabbbcc" result := minFreq(s1, s2) fmt.Printf("The minimum frequency of the smallest character is: %d\n", result) }
说明：
- 使用两个map来统计字符频次。
- 在遍历
s2的同时检查是否有s1中不存在的字符。- 找到并返回最小的频次。
复杂度分析
- 时间复杂度都是O(n + m)，其中n和m分别是两个字符串的长度。因为我们需要遍历两个字符串各一次来统计字符频次。
- 空间复杂度是O(k)，其中k是字符集的大小（对于ASCII字符集，k=256）。这是因为我们需要一个固定大小的数组或哈希表来存储每个字符的频次。
方式二
思路
我们可以先将两个字符串合并，然后统计合并后字符串中每个字符的出现频次。接着，找到最小的频次，并确保这个最小频次在两个原字符串中都有出现（即最小频次对应的字符在两个字符串中都有）。如果两个字符串中有不同的字符，则返回-1。
代码实现
Java版本
在Java中，可以使用HashMap来存储每个字符在两个字符串中出现的频次。之后，可以遍历HashMap找到共同存在的最小频次。
import java.util.HashMap; import java.util.Map; public class MinFrequency { /** * 找到两个字符串中共同存在的最小字符频次。 * 如果两个字符串有不同的字符，返回-1。 * * @param s1 第一个字符串 * @param s2 第二个字符串 * @return 最小字符频次，或-1（如果字符集不同） */ public static int minFreq(String s1, String s2) { // 使用HashMap存储字符频次，键为字符，值为字符在两个字符串中的频次对 Map<Character, int[]> freqMap = new HashMap<>(); // 遍历第一个字符串，统计字符频次（只记录频次，不区分字符串） for (char c : s1.toCharArray()) { freqMap.putIfAbsent(c, new int[2]); // 如果字符不存在，则初始化频次对为[0, 0] freqMap.get(c)[0]++; // 更新第一个字符串中的频次 } // 遍历第二个字符串，更新字符频次并检查字符是否存在于第一个字符串中 int minFreqCommon = Integer.MAX_VALUE; // 初始化最小共同频次为最大值 boolean hasDiffChar = false; // 标记是否有不同的字符 for (char c : s2.toCharArray()) { if (!freqMap.containsKey(c)) { hasDiffChar = true; // 如果字符在第一个字符串中不存在，标记为true continue; } freqMap.get(c)[1]++; // 更新第二个字符串中的频次 int minFreq = Math.min(freqMap.get(c)[0], freqMap.get(c)[1]); // 获取当前字符在两个字符串中的最小频次 minFreqCommon = Math.min(minFreqCommon, minFreq); // 更新最小共同频次 } // 如果两个字符串有不同的字符，返回-1 if (hasDiffChar) { return -1; } // 返回最小共同频次 return minFreqCommon == Integer.MAX_VALUE ? -1 : minFreqCommon; } public static void main(String[] args) { String s1 = "abcc"; String s2 = "aaabbbcc"; int result = minFreq(s1, s2); System.out.println("The minimum frequency of the smallest common character is: " + result); } }
说明：
- 在这个Java实现中，我们使用了
HashMap<Character, int[]>来存储每个字符在两个字符串中的频次对。int[]数组的第一个元素存储字符在s1中的频次，第二个元素存储字符在s2中的频次。- 我们首先遍历
s1来初始化freqMap，并只记录字符的频次，不区分它来自哪个字符串。然后，我们遍历s2，同时更新字符在s2中的频次，并检查字符是否存在于s1中。如果字符在s1中不存在，我们将hasDiffChar标记为true。同时，我们计算每个字符在两个字符串中的最小频次，并更新minFreqCommon为当前找到的最小值。- 最后，我们检查
hasDiffChar是否为true，如果是，则返回-1；否则，返回minFreqCommon作为最小共同频次。注意，如果minFreqCommon没有被任何字符的最小频次更新过（即仍然是初始值Integer.MAX_VALUE），我们也返回-1。
C语言版本
的C语言版本可以使用stdlib.h中的malloc和free来动态分配和释放内存，以及使用string.h中的函数来处理字符串。下面是一个简单的C语言实现，该实现使用哈希表来统计两个字符串中每个字符的频次，并找出最小共同频次。
请注意，C语言标准库并没有直接提供哈希表，因此我们需要自己实现一个简单的哈希表或者使用结构体数组来模拟哈希表的行为：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define HASH_SIZE 256 // 假设ASCII字符集 typedef struct { char ch; int freq1; // 字符在s1中出现的频次 int freq2; // 字符在s2中出现的频次 } CharFreq; CharFreq hashTable[HASH_SIZE]; // 初始化哈希表 void initHashTable() { memset(hashTable, 0, sizeof(hashTable)); } // 哈希函数，简单使用字符的ASCII值作为索引 unsigned int hash(char c) { return (unsigned int)c; } // 更新字符频次 void updateFreq(const char *str, int *freq) { for (int i = 0; str[i] != '\0'; i++) { unsigned int index = hash(str[i]); freq[index]++; } } // 找到最小共同频次 int findMinCommonFreq(const char *s1, const char *s2) { initHashTable(); int freq1[HASH_SIZE] = {0}; int freq2[HASH_SIZE] = {0}; // 更新s1中字符的频次 updateFreq(s1, freq1); // 更新s2中字符的频次，并查找最小共同频次 int minCommonFreq = INT_MAX; for (int i = 0; s2[i] != '\0'; i++) { unsigned int index = hash(s2[i]); if (freq1[index] == 0) { // 如果s2中的字符在s1中不存在，则无法找到共同频次 return -1; } int commonFreq = freq1[index] < freq2[index] ? freq1[index] : freq2[index]; minCommonFreq = commonFreq < minCommonFreq ? commonFreq : minCommonFreq; freq2[index]++; } return (minCommonFreq == INT_MAX) ? -1 : minCommonFreq; } int main() { const char *s1 = "abcc"; const char *s2 = "aaabbbcc"; int minFreq = findMinCommonFreq(s1, s2); if (minFreq != -1) { printf("The minimum frequency of the smallest common character is: %d\n", minFreq); } else { printf("No common character found in both strings.\n"); } return 0; }
说明：
这个C语言实现中，我们定义了一个
CharFreq结构体来存储字符和它在两个字符串中的频次。然而，为了简化代码，我们实际上没有使用这个结构体，而是使用了两个整型数组freq1和freq2来分别存储两个字符串中每个字符的频次。
hash函数简单地将字符的ASCII值作为哈希索引。在实际情况中，可能需要一个更复杂的哈希函数来减少哈希冲突。
updateFreq函数遍历字符串并更新对应字符的频次。
findMinCommonFreq函数首先初始化哈希表和频次数组，然后分别更新两个字符串中字符的频次，并查找最小共同频次。如果两个字符串中有不同的字符，则返回-1。在
main函数中，我们调用findMinCommonFreq并打印结果。如果结果为-1，则表示两个字符串中没有共同字符。
C++版本
由于c语言着实太麻烦了，下面单独补充c++的版本
#include <iostream> #include <string> #include <unordered_map> #include <algorithm> int minFreq(std::string s1, std::string s2) { std::string merged = s1 + s2; std::unordered_map<char, int> freqMap; int minFreq = INT_MAX; // 统计合并后字符串中每个字符的频次 for (char c : merged) { freqMap[c]++; } // 遍历频次映射，找到最小频次 for (const auto& pair : freqMap) { char c = pair.first; int freq = pair.second; // 检查最小频次对应的字符是否在两个字符串中都出现过 if (freqMap[c] >= merged.size() / 2 && freq < minFreq) { minFreq = freq; } } // 如果两个字符串有不同的字符，返回-1 if (s1.find_first_not_of(s2) != std::string::npos || s2.find_first_not_of(s1) != std::string::npos) { return -1; } return minFreq; } int main() { std::string s1 = "abcc"; std::string s2 = "aaabbbcc"; int result = minFreq(s1, s2); std::cout << "The minimum frequency of the smallest character is: " << result << std::endl; return 0; }
Python3版本
from collections import Counter def minFreq(s1: str, s2: str) -> int: merged = s1 + s2 freq_map = Counter(merged) min_freq = float('inf') # 找到最小频次，并检查该字符是否在两个字符串中都出现过 for char, freq in freq_map.items(): if freq >= len(merged) // 2 and freq < min_freq: min_freq = freq # 检查两个字符串是否有不同的字符 if set(s1) != set(s2): return -1 return min_freq # 示例 s1 = "abcc" s2 = "aaabbbcc" result = minFreq(s1, s2) print(f"The minimum frequency of the smallest character is: {result}")
Golang版本
package main import ( "fmt" ) func minFreq(s1, s2 string) int { merged := s1 + s2 freqMap := make(map[rune]int) minFreq := int(^uint(0) >> 1) // 统计合并后字符串中每个字符的频次 for _, ch := range merged { freqMap[ch]++ } // 遍历频次映射，找到最小频次 for _, freq := range freqMap { if freq >= len(merged)/2 && freq < minFreq { minFreq = freq } } // 检查两个字符串是否有不同的字符 if len(s1) != len(s2) || s1 != s2 { return -1 } return minFreq } func main() { s1 := "abcc" s2 := "aaabbbcc" result := minFreq(s1, s2) fmt.Printf("The minimum frequency of the smallest character is: %d\n", result) }
复杂度分析
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 方式一 | 不依赖内建函数，灵活性强，可适用于不同数据结构和需求 | 代码量较大，实现相对复杂，需要手动处理字符频次统计和比较 | O(m + n) | O(k)，其中k是字符集大小 |
| 方式二 | 代码简洁，易于理解，利用内建函数简化操作 | 依赖内建函数，可能不是最优解，合并字符串增加了空间和时间开销 | O(m + n) | O(m + n) |
| 优化后的方式二 | 避免了合并字符串的开销，直接在遍历过程中统计频次 | 仍然依赖内建函数，但减少了不必要的合并操作 | O(m + n) | O(k)，其中k是字符集大小 |
相似题目
这些题目都与字符频次统计、字符串比较和数组交集相关，可以通过类似的方法解决。在解决这些题目时，可以根据具体需求选择合适的方式，比如利用哈希表统计频次、使用排序或者双指针等技巧。
