我需要編寫一個函數(shù)來接收字符串并刪除相鄰的重復(fù)項。示例：輸入 -> “aabbaabbcccaaa”輸出 -> “ababca”我嘗試按如下方式解決：public String remdups(String input) { String response = ""; char temp; int i, length = input.length(); for(i = 0; i < length; i++) { temp = input.charAt(i); response += temp; while(i < length && input.charAt(i) == temp) i++; } return response;}但時間復(fù)雜度似乎沒有達(dá)到預(yù)期，我該如何提高性能或者有什么更好的方法？我知道這是一個非常簡單的問題，但我找不到改進(jìn)的方法或其他方法來做到這一點。
2 回答
白衣非少年
TA貢獻(xiàn)1155條經(jīng)驗 獲得超0個贊
對我來說，從復(fù)雜性的角度來看，您的代碼看起來已經(jīng)很好了。它只遍歷字符串一次。您可以對響應(yīng)進(jìn)行優(yōu)化，String使用 a StringBuilder，并且可能為了可讀性而稍微簡化循環(huán)（不需要 2 個嵌套循環(huán)，并且i從 2 個位置遞增計數(shù)器可能會引入錯誤）。
public String remdups(String input) {
StringBuilder response = new StringBuilder(input.length());
char temp;
for (int i = 0; i < input.length(); i++) {
char next = input.charAt(i);
if (temp != next) {
temp = next;
response.append(temp);
}
}
return response.toString();
}
一只甜甜圈
TA貢獻(xiàn)1836條經(jīng)驗 獲得超5個贊
為什么不嘗試使用正則表達(dá)式呢？就像這樣：
public static void main(String[] args) {
String str = "aabbaabbcccaaa";
System.out.println(str.replaceAll("(.)\\1+","$1"));
}輸出：
ababca
編輯：
為了將來的參考，這種方法被證明是非常慢的。我使用 JMH 對它進(jìn)行了基準(zhǔn)測試，對于短字符串，它比非正則表達(dá)式解決方案慢大約 4 倍，并且對于較長（約 10k 個字符）的字符串只會變得更糟。
添加回答
舉報
0/150
提交
取消