我正在解決CodeSignal的問題：
給定 a
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 '_';
}
uj5u.com熱心網友回復：
此任務的最小可能時間復雜度是線性O(n)，因為我們需要檢查給定字串中的每個字符以找出特定字符是否唯一。
您當前的解決方案在O(n^2)中運行-Collections.frequency()迭代字串中的所有字符，并且此迭代和此方法對每個字符呼叫。這基本上是一個蠻力實作。
我們可以生成一個 map Map<Character,Boolean>，它將每個字符與一個boolean表示它是否重復的值相關聯。
這將允許避免多次迭代給定的字串。
然后我們需要遍歷鍵集以找到第一個不重復的字符。由于該Map實作LinkedHashMap用于確保回傳的非重復字符將是給定字串中第一個遇到的字符。
要更新MapI've used Java 8 method merge()，它需要三個引數：一個key、一個value和一個負責合并舊值和新值的函式。
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('_');
}
uj5u.com熱心網友回復：
這是一種稍微不同的方法，既使用 aSet來說明重復，又使用 aQueue在發現可能的重復之前保留候選人。
- 遍歷字串列。
- 嘗試將角色添加到
seen集合中。如果還沒有，也將其添加到candidates佇列中。 - 否則，如果是
"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();
}
我已經對此進行了相當廣泛的測驗，但它還沒有失敗。它也相對非常有效。但正如可能發生的那樣，我可能忽略了一些事情。
uj5u.com熱心網友回復：
一種技術是使用每個字符的頻率/計數陣列的 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 個字母）。這在非英文字母的其他場景中不起作用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505894.html