如何查找給定字符串中的第一個字符，該字符只出現一次

Question

這是一個面試問題。查找給定字符串中的第一個字符，只出現一次（我認爲解決方案應該在Java中）。

例如：

 
"babcbcd" -> 'a' // both 'a' and 'd' appear only once but 'a' appears before 'd' 

平凡解是

• 構建地圖（例如HashMap）：字符 - >它的字符串中的出現次數;
• 掃描對地圖字符串和測試字符串中的字符，直到字符的值是1

是否有意義？什麼是最好的圖的實現？有沒有更好的，更有效的解決方案？

Answer 1

這是Haskell的一個版本。

import Data.List (elemIndices) 
firstSingle str = take 1 [a | a <- str, length (elemIndices a str) == 1] 

*主要Data.List模塊> firstSingle 「babcbcd」
「一」

Answer 2

在Java中，您可以使用LinkedHashMap<Character,Integer>來計算每個字符出現在字符串中的次數。由於LinkedHashMap保留了插入順序，因此您可以迭代其條目以查找剛好出現一次的第一個字符。

根據合理的假設，這將給出O(n)解決方案。

Answer 3

您可以在原始字符串的一次傳遞中做到這一點：創建一個鏈接哈希圖，存儲您迄今爲止找到的字符的計數。然後瀏覽地圖條目（它將按照插入順序，因爲它是一個鏈接的地圖），並在您看到一個計數時停止。

Answer 4

你已經找到了一個很好的解決方案，但如果你想我提出一個不同的方法：

final String abc = "abcdefg....z"; 
boolean scanned[] = new boolean[abc.lenght()]; 
//set all to false ... 
for(int i = 0; i<yourString.lenght(); i++){ 
    char c = yourString.charAt(i); 
    if(!scanned[abc.indexOf(c)]){ 
     for(int j=i+1; j<yourString.lenght(); j++) 
      if(yourString.charAt(i) == c){ // founded another 
       scanned[abc.indexOf(c)] = true; 
       break; 
      } 
     if(!scanned[abc.indexOf(c)]) 
      return c; 
    } 
} 

Answer 5

上述所有的解決方案都需要爲O（n）memory.In爲了做到在O（1）內存你可以爲所有字符運行一個for循環（在ASCII中有128），並計算外觀和第一次出現的次數，然後找到非重複的字符。時間複雜度O（128 | s |）。

int min=Integer.MAX_VALUE; 
char ans=' '; //any initialization 
for (i=0; i<128;i++){ 
    int count=0,first=-1; 
    for(j=0;j<s.length();j++){ 
     if(s.charAt(j)==(char)(i)) count++; 
     if(count==1) first=j; 
     if(count>1) break; 
    } 
    if(count==1 && min>first){ 
     first=min;ans=s.charAt(first); 
    } 
} 
if(min!=Integer.MAX_VALUE) System.out.println(ans); 
else System.out.println("No such char found"); 

Answer 6

假設String僅由A-Z字符，你可以使用迄今所看到的字符的隊列，並保持計數。

public static String findFirstLetterThatAppearsOnceInString(String str) { 
    int[] seenCount = new int[26]; 
    int[] queue = new int[26]; 
    int queueSize = 0; 
    for (char c : str.toCharArray()) { // Iterate over the input characters 
     int i = c-'a'; 
     if (seenCount[i]<2) { 
      seenCount[i]++; 
      // If seen for the first time, store it in queue 
      if (seenCount[i]==1) queue[queueSize++]=i; 
     } 
    } 
    for (int qi=0;qi<queueSize;qi++) if (seenCount[queue[qi]]==1) return (char)(queue[qi]+'a')+""; 
    return null; 
} 

Answer 7

如果我面試，我會希望（儘管不一定是期待）是這樣的：

def string = 'babcbcd' 
def singles = string.toList().groupBy{ it }.findAll{ it.value.size() == 1 }.collect{ it.key } 
println "First char that appears once: " + string.find{ singles.contains it } 

的關鍵是中間路線。它將字符串作爲字符列表，因此您可以過濾掉任何只發生一次的字符，最後生成一次出現的字符列表。然後我們只搜索該列表中第一個字符的字符串。

它是Groovy，因爲它不可能在Java中變得優雅。也許一旦JDK 8終於讓它...

更新：更簡潔的版本，靈感來源於@groovy's Haskell solution。我幾乎爲現在第一個人的笨拙感到尷尬:)

def firstUnique(seq) { seq.findAll{ seq.count(it) == 1 }.first() } 

Answer 8

簡單，無地圖解決方案，假設沒有Unicode：

public String firstLonelyChar(String input) 
{ 
    while(input.length() > 0) 
    { 
     int curLength = input.length(); 
     String first = String.valueOf(input.charAt(0)); 
     input = input.replaceAll(first, ""); 
     if(input.length() == curLength - 1) 
      return first; 
    } 
    return null; 
}