如何查找给定字符串中的第一个字符，该字符只出现一次

这是一个面试问题。查找给定字符串中的第一个字符，只出现一次（我认为解决方案应该在Java中）。如何查找给定字符串中的第一个字符，该字符只出现一次

例如：

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

平凡解是

构建地图（例如HashMap）：字符 - >它的字符串中的出现次数;
扫描对地图字符串和测试字符串中的字符，直到字符的值是1

是否有意义？什么是最好的图的实现？有没有更好的，更有效的解决方案？

来源

2013-02-17 Michael

*“有没有更好的，更有效的解决方案？“*你认为什么？ – 2013-02-17 15:08:19

_是否有更好，更有效的解决方案？_我不这么认为。 – sigod 2013-02-17 15:10:49

你可以保持一个优先级队列，并弹出顶部并检查它是否为1. – 2013-02-17 15:11:26

这是Haskell的一个版本。

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

*主要Data.List模块> firstSingle “babcbcd”
“一”

来源

2013-02-17 20:14:55

+1不错。我喜欢。 – 2013-02-17 21:46:35

@RyanStewart ...你给了我灵感;） – 2013-02-17 21:49:47

哈哈，反之亦然。看看[我的更新]（http://stackoverflow.com/a/14923631/839646）。我一直认为必须有一个更简单的方法。 – 2013-02-17 22:02:13

在Java中，您可以使用LinkedHashMap<Character,Integer>来计算每个字符出现在字符串中的次数。由于LinkedHashMap保留了插入顺序，因此您可以迭代其条目以查找刚好出现一次的第一个字符。

根据合理的假设，这将给出O(n)解决方案。

来源

2013-02-17 15:10:48 NPE

您可以在原始字符串的一次传递中做到这一点：创建一个链接哈希图，存储您迄今为止找到的字符的计数。然后浏览地图条目（它将按照插入顺序，因为它是一个链接的地图），并在您看到一个计数时停止。

来源

2013-02-17 15:13:12 dasblinkenlight

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

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; 
    } 
}

来源

2013-02-17 15:37:38 Giudark

上述所有的解决方案都需要为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");

来源

2013-02-17 15:59:59

在unicode中，有超过256个字符。你的解决方案并不比链接的哈希映射好得多。是的，您没有维护地图结构的管理开销，但是在最糟糕的情况下，您的解决方案和hashmaps都需要一个“Integer”计数器来存储每个可能的字符。更糟的是：hashmaps只需要每个字符出现一个，而你的字母表中的每个字符都需要一个 - 对于像unicode这样的大字母很重要。 – us2012 2013-02-17 16:04:40

@ us2012：看看我是如何在O（1）内存中完成的。答：是的，它应该是ASCII。谢谢。我已纠正它。 – 2013-02-18 07:10:01

假设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; 
}

来源

2013-02-17 16:27:28 StatsTrade

如果我面试，我会希望（尽管不一定是期待）是这样的：

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() }

来源

2013-02-17 17:04:16

简单，无地图解决方案，假设没有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; 
}

来源

2013-02-17 20:54:56 Geobits

如何查找给定字符串中的第一个字符，该字符只出现一次

回答

相关问题