在给定字符串中查找第一个非重复字符，由于超时，无法通过一些测试用例

Question

我正在处理CodeSignal:中的一个问题

给定仅由字母表组成的String s，首先返回非重复元素。否则，返回'-'。

示例：输入-s="abacabad"，输出-'c'。

我想出了以下代码。它只通过16/19测试用例。在O(n(或

O(1(我的代码：

public char solution(String s) {
ArrayList<Character> hs = new ArrayList<>();

for (char c:s.toCharArray()) {
hs.add(c);
}

for (int j=0; j<s.length(); j++) {
if ( 1 == Collections.frequency(hs, s.charAt(j))) {
return s.charAt(j);
}
}

return '_';
}

Answer 1

此任务的最小时间复杂度是线性的O(n(，因为我们需要检查给定字符串中的每个字符，以确定特定字符是否唯一。

您当前的解决方案运行在O(n^2(-Collections.frequency()迭代字符串中的所有字符，并对每个字符调用此迭代和方法。这基本上是一个暴力的实现。

我们可以生成一个映射Map<Character,Boolean>，它将每个字符与一个表示是否重复的boolean值相关联。

这样就可以避免对给定的字符串进行多次迭代。

然后，我们需要对密钥集进行迭代，以找到第一个不重复的字符。作为Map实现，LinkedHashMap用于确保返回的非重复字符将是给定字符串中第一个遇到的字符。

为了更新Map，我使用了Java 8方法merge()，它需要三个参数：键、值，以及负责合并旧值和新值

public char solution(String s) {
Map<Character, Boolean> isNonRepeated = getMap(s);

for (Map.Entry<Character, Boolean> entry: isNonRepeated.entrySet()) {
if (entry.getValue()) {
return entry.getKey();
}
}        

return '_';
}
public Map<Character, Boolean> getMap(String s) {
Map<Character, Boolean> isNonRepeated = new LinkedHashMap<>();

for (int i = 0; i < s.length(); i++) {
isNonRepeated.merge(s.charAt(i), true, (v1, v2) -> false);
}
return isNonRepeated;
}

如果你对流很满意，这个问题可以用一句话来解决(算法保持不变，时间复杂度也是线性的(：

public char solution(String s) {

return s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.toMap( // creates intermediate Map<Character, Boolean>
Function.identity(),   // key
c -> true,             // value - first occurrence, character is considered to be non-repeated
(v1, v2) -> false,     // resolving values, character is proved to be a duplicate
LinkedHashMap::new
))
.entrySet().stream()
.filter(Map.Entry::getValue)
.findFirst()
.map(Map.Entry::getKey)
.orElse('_');
}

Answer 2

这里有一种略有不同的方法，既使用Set来说明重复项，也使用Queue来在发现可能的重复项之前保存候选项。

• 遍历字符列表
• 尝试将该字符添加到seen集合中。如果还没有，也将其添加到CCD_ 16队列中
• 否则，如果它是"seen"，请尝试将其从候选队列中删除
• 完成此操作时，队列的头应该包含第一个不重复的字符。如果队列为空，则返回默认值，因为未找到唯一字符

public char solution(String s) {
Queue<Character> candidates = new LinkedList<>();
Set<Character> seen = new HashSet<>();
for (char c : s.toCharArray()) {
if (seen.add(c)) {
candidates.add(c);
} else  {
candidates.remove(c);
}
}
return candidates.isEmpty() ? '_' : candidates.peek();
}

我已经做了相当广泛的测试，它还没有失败。它也比较高效。但正如可能发生的那样，我可能忽略了一些事情。

Answer 3

一种技术是为每个字符使用频率/计数数组的2遍解决方案。

public static char firstNonRepeatingChar(String s) {
int[] frequency = new int[26]; // this is O(1) space complexity because alphabet is finite of 26 letters

/* First Pass - Fill our frequency array */
for(int i = 0; i < s.length(); i++) {
frequency[s.charAt(i) - 'a']++;
}
/* Second Pass - Look up our frequency array */
for(int i = 0; i < s.length(); i++) {
if(frequency[s.charAt(i) - 'a'] == 1) {
return s.charAt(i);
}
}
/* Not Found */
return '_';
}

这个解是O(2n(->O(n(和O(1(的空间复杂性，因为我们使用的是英语字母表的有限集合(26个字母(。这在其他非英语字母的情况下是不起作用的。