2

这是一道面试题。找到给定字符串中的第一个字符，它只出现一次（我想解决方案应该是 Java）。

例如：

"babcbcd" -> 'a' // 'a' 和 'd' 都只出现一次，但 'a' 出现在 'd' 之前

简单的解决方案是

  • 构建地图（例如HashMap）：char -> 它在字符串中出现的次数；
  • 针对映射扫描字符串并测试字符串字符，直到字符的值为1。

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

4

8 回答 8

3

这是 Haskell 中的一个版本。

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

*Main Data.List> firstSingle "babcbcd"
"a"

于 2013-02-17T20:14:55.900 回答
3

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

在合理的假设下，这将给出一个O(n)解决方案。

于 2013-02-17T15:10:48.737 回答
2

如果我在面试，我会希望（虽然不一定期待）这样的事情：

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 的 Haskell 解决方案。我现在几乎为我的第一个笨拙而尴尬:)

def firstUnique(seq) { seq.findAll{ seq.count(it) == 1 }.first() }
于 2013-02-17T17:04:16.037 回答
1

所有上述解决方案都需要 O(n) 内存。为了在 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-17T15:59:59.333 回答
1

假设String仅由 az 个字符组成，您可以对目前看到的字符使用队列并保持计数。

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-17T16:27:28.000 回答
1

简单的非地图解决方案，假设没有 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-17T20:54:56.447 回答
1

您可以在原始字符串的一次传递中完成：制作一个链接的哈希映射，存储您到目前为止找到的字符的计数。然后浏览地图条目（它将按插入顺序排列，因为它是一个链接地图）并在看到计数为 1 时停止。

于 2013-02-17T15:13:12.793 回答
1

您已经找到了一个很好的解决方案，但如果您愿意，我建议采用不同的方法：

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-17T15:37:38.717 回答