现用一台2G内存4核CPU的电脑,尽可能快速的找出3.7亿个字中第一个不重复的字符,Java代码利用多线程分治实现
时间: 2023-05-30 12:02:00 浏览: 131
java 判断字符串中是否有重复字符的示例
以下是Java代码,利用多线程分治实现查找第一个不重复的字符:
```java
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.*;
public class FirstNonRepeatedCharacter {
public static char findFirstNonRepeatedChar(String str) throws ExecutionException, InterruptedException {
int numThreads = Runtime.getRuntime().availableProcessors();
ExecutorService pool = Executors.newFixedThreadPool(numThreads);
int chunkSize = str.length() / numThreads;
int startIndex = 0;
int endIndex = chunkSize;
Map<Character, Integer> charCountMap = new HashMap<>();
while (startIndex < str.length()) {
if (endIndex > str.length()) {
endIndex = str.length();
}
String chunk = str.substring(startIndex, endIndex);
Future<Map<Character, Integer>> future = pool.submit(new CountCharsTask(chunk));
Map<Character, Integer> chunkCountMap = future.get();
for (Map.Entry<Character, Integer> entry : chunkCountMap.entrySet()) {
char ch = entry.getKey();
int count = entry.getValue();
if (charCountMap.containsKey(ch)) {
charCountMap.put(ch, charCountMap.get(ch) + count);
} else {
charCountMap.put(ch, count);
}
}
startIndex += chunkSize;
endIndex += chunkSize;
}
pool.shutdown();
for (char ch : str.toCharArray()) {
if (charCountMap.get(ch) == 1) {
return ch;
}
}
return Character.MIN_VALUE;
}
private static class CountCharsTask implements Callable<Map<Character, Integer>> {
private final String chunk;
public CountCharsTask(String chunk) {
this.chunk = chunk;
}
@Override
public Map<Character, Integer> call() throws Exception {
Map<Character, Integer> countMap = new HashMap<>();
for (char ch : chunk.toCharArray()) {
if (countMap.containsKey(ch)) {
countMap.put(ch, countMap.get(ch) + 1);
} else {
countMap.put(ch, 1);
}
}
return countMap;
}
}
public static void main(String[] args) {
String str = "abacabadabacaba";
try {
char firstNonRepeatedChar = findFirstNonRepeatedChar(str);
System.out.println("First non-repeated character: " + firstNonRepeatedChar);
} catch (ExecutionException | InterruptedException e) {
e.printStackTrace();
}
}
}
```
这个代码首先根据可用的处理器核心数创建一个固定大小的线程池。然后,将输入字符串分成多个块,每个块都由一个线程处理。每个线程计算块中每个字符出现的次数,并将其存储在一个映射中。最后,对所有映射进行合并,并查找第一个不重复的字符。如果找到了一个不重复的字符,则返回该字符;否则,返回`Character.MIN_VALUE`。
阅读全文