在字符串中找到第一个非重复字符。

What is the quickest way to find the first character which only appears once in a string?

找到第一个只出现在字符串中的字符的最快方法是什么?

34 个解决方案

#1

You can't know that the character is un-repeated until you've processed the whole string, so my suggestion would be this:

你不知道这个字符是不重复的，直到你处理了整个字符串，所以我的建议是:

def first_non_repeated_character(string):
  chars = []
  repeated = []
  for character in string:
    if character in chars:
      chars.remove(character)
      repeated.append(character)
    else:
      if not character in repeated:
        chars.append(character)
  if len(chars):
    return chars[0]
  else:
    return False

Edit: originally posted code was bad, but this latest snippet is Certified To Work On Ryan's Computer™.

编辑:最初发布代码不好,但这一最新片段瑞安认证工作的计算机™。

#2

It has to be at least O(n) because you don't know if a character will be repeated until you've read all characters.

它至少应该是O(n)因为你不知道一个字符是否会重复，直到你读了所有的字符。

So you can iterate over the characters and append each character to a list the first time you see it, and separately keep a count of how many times you've seen it (in fact the only values that matter for the count is "0", "1" or "more than 1").

因此，您可以遍历这些字符，并在第一次看到它时将每个字符追加到一个列表中，并分别保存您所看到的次数(实际上，惟一重要的值是“0”、“1”或“大于1”)。

When you reach the end of the string you just have to find the first character in the list that has a count of exactly one.

当你到达字符串的末尾时，你只需要找到列表中的第一个字符，它有一个精确的计数。

---

Example code in Python:

Python示例代码:

def first_non_repeated_character(s):
    counts = defaultdict(int)
    l = []
    for c in s:
        counts[c] += 1
        if counts[c] == 1:
            l.append(c)

    for c in l:
        if counts[c] == 1:
            return c

    return None

This runs in O(n).

这在O(n)。

#3

Why not use a heap based data structure such as a minimum priority queue. As you read each character from the string, add it to the queue with a priority based on the location in the string and the number of occurrences so far. You could modify the queue to add priorities on collision so that the priority of a character is the sum of the number appearances of that character. At the end of the loop, the first element in the queue will be the least frequent character in the string and if there are multiple characters with a count == 1, the first element was the first unique character added to the queue.

为什么不使用基于堆的数据结构，比如最小优先级队列。当您从字符串中读取每个字符时，将它添加到队列中，并根据字符串中的位置和到目前为止出现的次数将其添加到队列中。您可以修改队列以在冲突中添加优先级，这样一个字符的优先级就是该字符的数量外观的总和。在循环结束时，队列中的第一个元素将是字符串中最不频繁的字符，如果有多个字符与count == 1，那么第一个元素就是添加到队列中的第一个惟一字符。

#4

Here is another fun way to do it. Counter requires Python2.7 or Python3.1

这是另一种有趣的方法。Counter需要Python2.7或Python3.1。

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     return min((k for k,v in Counter(s).items() if v<2), key=s.index)
...
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

#5

Lots of answers are attempting O(n) but are forgetting the actual costs of inserting and removing from the lists/associative arrays/sets they're using to track.

很多的答案都在尝试O(n)，但是忘记了从列表/关联数组/集合中插入和移除的实际代价。

If you can assume that a char is a single byte, then you use a simple array indexed by the char and keep a count in it. This is truly O(n) because the array accesses are guaranteed O(1), and the final pass over the array to find the first element with 1 is constant time (because the array has a small, fixed size).

如果可以假定char是单个字节，那么就使用由char索引的简单数组，并在其中保持计数。这是真正的O(n)，因为数组访问是有保证的O(1)，并且最终通过数组来查找第一个元素为1的元素是常量时间(因为数组有一个小的、固定的大小)。

If you can't assume that a char is a single byte, then I would propose sorting the string and then doing a single pass checking adjacent values. This would be O(n log n) for the sort plus O(n) for the final pass. So it's effectively O(n log n), which is better than O(n^2). Also, it has virtually no space overhead, which is another problem with many of the answers that are attempting O(n).

如果不能假定char是单个字节，那么我将建议对字符串进行排序，然后对相邻的值进行一次检查。这是O(n log n)的排序加上O(n)的最后通关。这是有效的O(n log n),这是比O(n ^ 2)。而且，它几乎没有空间开销，这是另一个问题，许多的答案正在尝试O(n)。

#6

Counter requires Python2.7 or Python3.1

Counter需要Python2.7或Python3.1。

>>> from collections import Counter
>>> def first_non_repeated_character(s):
...     counts = Counter(s)
...     for c in s:
...         if counts[c]==1:
...             return c
...     return None
... 
>>> first_non_repeated_character("aaabbbcddd")
'c'
>>> first_non_repeated_character("aaaebbbcddd")
'e'

#7

Refactoring a solution proposed earlier (not having to use extra list/memory). This goes over the string twice. So this takes O(n) too like the original solution.

重构之前提出的解决方案(不必使用额外的列表/内存)。这条线穿过弦两次。这就像原来的解一样。

def first_non_repeated_character(s):
    counts = defaultdict(int)
    for c in s:
        counts[c] += 1
    for c in s:
        if counts[c] == 1:
            return c
    return None

#8

The following is a Ruby implementation of finding the first nonrepeated character of a string:

下面是找到字符串的第一个非重复字符的Ruby实现:

def first_non_repeated_character(string)
  string1 = string.split('')
  string2 = string.split('')

  string1.each do |let1|
    counter = 0
    string2.each do |let2|
      if let1 == let2
        counter+=1
      end
    end
  if counter == 1 
    return let1
    break
  end
end
end

p first_non_repeated_character('dont doddle in the forest')

And here is a JavaScript implementation of the same style function:

这里是一个JavaScript实现的相同样式函数:

var first_non_repeated_character = function (string) {
  var string1 = string.split('');
  var string2 = string.split('');

  var single_letters = [];

  for (var i = 0; i < string1.length; i++) {
    var count = 0;
    for (var x = 0; x < string2.length; x++) {
      if (string1[i] == string2[x]) {
        count++
      }
    }
    if (count == 1) {
      return string1[i];
    }
  }
}

console.log(first_non_repeated_character('dont doddle in the forest'));
console.log(first_non_repeated_character('how are you today really?'));

In both cases I used a counter knowing that if the letter is not matched anywhere in the string, it will only occur in the string once so I just count it's occurrence.

在这两种情况下，我使用一个计数器，知道如果字符串中没有匹配字母，那么它只会在字符串中出现一次，所以我只计算它的出现次数。

#9

I think this should do it in C. This operates in O(n) time with no ambiguity about order of insertion and deletion operators. This is a counting sort (simplest form of a bucket sort, which itself is the simple form of a radix sort).

我认为这应该在c中完成，这在O(n)时间内操作，对于插入和删除操作符的顺序没有歧义。这是计数排序(bucket排序的最简单形式，它本身就是基数排序的简单形式)。

unsigned char find_first_unique(unsigned char *string)
{
    int chars[256];
    int i=0;
    memset(chars, 0, sizeof(chars));

    while (string[i++])
    {
        chars[string[i]]++;
    }

    i = 0;
    while (string[i++])
    {
        if (chars[string[i]] == 1) return string[i];
    }
    return 0;
}

#10

In Ruby:

在Ruby中:

(Original Credit: Andrew A. Smith)

(原信用证:安德鲁·a·史密斯)

x = "a huge string in which some characters repeat"

def first_unique_character(s)
 s.each_char.detect { |c| s.count(c) == 1 }
end

first_unique_character(x)
=> "u"

#11

def first_non_repeated_character(string):
  chars = []
  repeated = []
  for character in string:
    if character in repeated:
        ... discard it.
    else if character in chars:
      chars.remove(character)
      repeated.append(character)
    else:
      if not character in repeated:
        chars.append(character)
  if len(chars):
    return chars[0]
  else:
    return False

#12

Other JavaScript solutions are quite c-style solutions here is a more JavaScript-style solution.

其他的JavaScript解决方案都是c风格的解决方案，这是一个更加JavaScript风格的解决方案。

var arr = string.split("");
var occurences = {};
var tmp;
var lowestindex = string.length+1;

arr.forEach( function(c){ 
  tmp = c;
  if( typeof occurences[tmp] == "undefined")
    occurences[tmp] = tmp;
  else 
    occurences[tmp] += tmp;
});


for(var p in occurences) {
  if(occurences[p].length == 1)
    lowestindex = Math.min(lowestindex, string.indexOf(p));
}

if(lowestindex > string.length)
  return null;

return string[lowestindex];

}

#13

in C, this is almost Shlemiel the Painter's Algorithm (not quite O(n!) but more than 0(n2)).

在C语言中，这几乎是画家的算法(不完全是O(n!)，而是大于0(n2))。

But will outperform "better" algorithms for reasonably sized strings because O is so small. This can also easily tell you the location of the first non-repeating string.

但是对于合理大小的字符串，它的性能优于“更好”的算法，因为O是如此之小。这也可以很容易地告诉您第一个非重复字符串的位置。

char FirstNonRepeatedChar(char * psz)
{
   for (int ii = 0; psz[ii] != 0; ++ii)
   {
      for (int jj = ii+1; ; ++jj)
      {
         // if we hit the end of string, then we found a non-repeat character.
         //
         if (psz[jj] == 0)
            return psz[ii]; // this character doesn't repeat

         // if we found a repeat character, we can stop looking.
         //
         if (psz[ii] == psz[jj])
            break; 
      }
   }

   return 0; // there were no non-repeating characters.
}

edit: this code is assuming you don't mean consecutive repeating characters.

编辑:此代码假定您不是指连续重复字符。

#14

Here's an implementation in Perl (version >=5.10) that doesn't care whether the repeated characters are consecutive or not:

这里是Perl的一个实现(版本>=5.10)，它不关心重复字符是否连续:

use strict;
use warnings;

foreach my $word(@ARGV)
{
  my @distinct_chars;
  my %char_counts;

  my @chars=split(//,$word);

  foreach (@chars)
  {
    push @distinct_chars,$_ unless $_~~@distinct_chars;
    $char_counts{$_}++;
  }

  my $first_non_repeated="";

  foreach(@distinct_chars)
  {
    if($char_counts{$_}==1)
    {
      $first_non_repeated=$_;
      last;
    }
  }

  if(length($first_non_repeated))
  {
    print "For \"$word\", the first non-repeated character is '$first_non_repeated'.\n";
  }
  else
  {
    print "All characters in \"$word\" are repeated.\n";
  }
}

Storing this code in a script (which I named non_repeated.pl) and running it on a few inputs produces:

将此代码存储在脚本中(我将其命名为non_repeat. pl)并在一些输入上运行它:

jmaney> perl non_repeated.pl aabccd "a huge string in which some characters repeat" abcabc
For "aabccd", the first non-repeated character is 'b'.
For "a huge string in which some characters repeat", the first non-repeated character is 'u'.
All characters in "abcabc" are repeated.

#15

Here's a possible solution in ruby without using Array#detect (as in this answer). Using Array#detect makes it too easy, I think.

这里有一个可能的解决方案，在ruby中没有使用数组#检测(在这个答案中)。我认为，使用数组#检测使它太容易了。

ALPHABET = %w(a b c d e f g h i j k l m n o p q r s t u v w x y z)

def fnr(s)
  unseen_chars    = ALPHABET.dup
  seen_once_chars = []
  s.each_char do |c|
    if unseen_chars.include?(c)
      unseen_chars.delete(c)
      seen_once_chars << c
    elsif seen_once_chars.include?(c)
      seen_once_chars.delete(c)
    end
  end

  seen_once_chars.first
end

Seems to work for some simple examples:

似乎为一些简单的例子而工作:

fnr "abcdabcegghh"
# => "d"

fnr "abababababababaqababa"                                    
=> "q"

Suggestions and corrections are very much appreciated!

非常感谢您的建议和更正!

#16

Try this code:

试试这段代码:

    public static String findFirstUnique(String str)
    {
        String unique = "";

        foreach (char ch in str)
        {
            if (unique.Contains(ch)) unique=unique.Replace(ch.ToString(), "");
            else unique += ch.ToString();
        }
        return unique[0].ToString();
    }

#17

In Mathematica one might write this:

在Mathematica，你可以这样写:

string = "conservationist deliberately treasures analytical";

Cases[Gather @ Characters @ string, {_}, 1, 1][[1]]

{"v"}

#18

This snippet code in JavaScript

这段代码是JavaScript代码。

var string = "tooth";
var hash = [];
for(var i=0; j=string.length, i<j; i++){
    if(hash[string[i]] !== undefined){
        hash[string[i]] = hash[string[i]] + 1;
    }else{
        hash[string[i]] = 1;
    }
}

for(i=0; j=string.length, i<j; i++){
    if(hash[string[i]] === 1){
        console.info( string[i] );
        return false;
    }
}
// prints "h"

#19

Different approach here. scan each element in the string and create a count array which stores the repetition count of each element. Next time again start from first element in the array and print the first occurrence of element with count = 1

不同的方法。扫描字符串中的每个元素并创建一个计数数组，该数组存储每个元素的重复计数。下次再从数组的第一个元素开始，然后打印第一个元素的出现，count = 1。

C code 
-----
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    char t_c;
    char *t_p = argv[1] ;
    char count[128]={'\0'};
    char ch;

    for(t_c = *(argv[1]); t_c != '\0'; t_c = *(++t_p))
        count[t_c]++;
    t_p = argv[1];
    for(t_c = *t_p; t_c != '\0'; t_c = *(++t_p))
    {
        if(count[t_c] == 1)
        {
            printf("Element is %c\n",t_c);
            break;
        }
    }

return 0;    
} 

#20

input is = aabbcddeef output is = c

输入= aabbcddeef输出= c。

char FindUniqueChar(char *a)
{
    int i=0;
    bool repeat=false;
    while(a[i] != '\0')
    {
      if (a[i] == a[i+1])
      {
        repeat = true;
      }
      else
      {
            if(!repeat)
            {
            cout<<a[i];
            return a[i];
            }
        repeat=false;
      }
      i++;
    }
    return a[i];
}

#21

Here is another approach...we could have a array which will store the count and the index of the first occurrence of the character. After filling up the array we could jst traverse the array and find the MINIMUM index whose count is 1 then return str[index]

这是另一种方法…我们可以有一个数组，它将存储该字符的第一次出现的计数和索引。在填充数组之后，我们可以遍历数组并找到最小索引，其count为1，然后返回str[索引]

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>
using namespace std;

#define No_of_chars 256

//store the count and the index where the char first appear
typedef struct countarray
{
    int count;
    int index;
}countarray;

//returns the count array
    countarray *getcountarray(char *str)
    {
        countarray *count;
        count=new countarray[No_of_chars];
        for(int i=0;i<No_of_chars;i++)
        {
            count[i].count=0;
            count[i].index=-1;
        }
        for(int i=0;*(str+i);i++)
        {
            (count[*(str+i)].count)++;
            if(count[*(str+i)].count==1) //if count==1 then update the index
                count[*(str+i)].index=i; 

        }
        return count;
    }

    char firstnonrepeatingchar(char *str)
    {
        countarray *array;
        array = getcountarray(str);
        int result = INT_MAX;
        for(int i=0;i<No_of_chars;i++)
        {
            if(array[i].count==1 && result > array[i].index)
                result = array[i].index;
        }
        delete[] (array);
        return (str[result]);
    }

    int main()
    {
        char str[] = "geeksforgeeks";
        cout<<"First non repeating character is "<<firstnonrepeatingchar(str)<<endl;        
        return 0;
    }

#22

Function:

功能:

This c# function uses a HashTable (Dictionary) and have a performance O(2n) worstcase.

这个c#函数使用一个HashTable(字典)并有一个性能O(2n) worstcase。

private static string FirstNoRepeatingCharacter(string aword)
    {
        Dictionary<string, int> dic = new Dictionary<string, int>();            

        for (int i = 0; i < aword.Length; i++)
        {
            if (!dic.ContainsKey(aword.Substring(i, 1)))
                dic.Add(aword.Substring(i, 1), 1);
            else
                dic[aword.Substring(i, 1)]++;
        }

        foreach (var item in dic)
        {
            if (item.Value == 1) return item.Key;
        }
        return string.Empty;
    }

Example:

例子:

string aword = "TEETER";

字符串个说法=“摇摇欲坠”;

Console.WriteLine(FirstNoRepeatingCharacter(aword)); //print: R

Console.WriteLine(FirstNoRepeatingCharacter(个说法));/ /打印:R

#23

I have two strings i.e. 'unique' and 'repeated'. Every character appearing for the first time, gets added to 'unique'. If it is repeated for the second time, it gets removed from 'unique' and added to 'repeated'. This way, we will always have a string of unique characters in 'unique'. Complexity big O(n)

我有两个字符串。“独特”和“重复”。第一次出现的每个角色都被添加到“unique”中。如果第二次重复，则从“unique”中删除，并添加到“repeat”中。这样，我们就会在“unique”中有一串独特的字符。复杂性大O(n)

public void firstUniqueChar(String str){
    String unique= "";
    String repeated = "";
    str = str.toLowerCase();
    for(int i=0; i<str.length();i++){
        char ch = str.charAt(i);
        if(!(repeated.contains(str.subSequence(i, i+1))))
            if(unique.contains(str.subSequence(i, i+1))){
                unique = unique.replaceAll(Character.toString(ch), "");
                repeated = repeated+ch;
            }
            else
                unique = unique+ch;
    }
    System.out.println(unique.charAt(0));
}

#24

The following code is in C# with complexity of n.

下面的代码是c#，复杂度为n。

using System;
using System.Linq;
using System.Text;

namespace SomethingDigital
{
    class FirstNonRepeatingChar
    {
        public static void Main()
        {
            String input = "geeksforgeeksandgeeksquizfor";
            char[] str = input.ToCharArray();

            bool[] b = new bool[256];
            String unique1 = "";
            String unique2 = "";

            foreach (char ch in str)
            {
                if (!unique1.Contains(ch))
                {
                    unique1 = unique1 + ch;
                    unique2 = unique2 + ch;
                }
                else
                {
                    unique2 = unique2.Replace(ch.ToString(), "");
                }
            }
            if (unique2 != "")
            {
                Console.WriteLine(unique2[0].ToString());
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("No non repeated string");
                Console.ReadLine();
            }
        }
    }
}

#25

The following solution is an elegant way to find the first unique character within a string using the new features which have been introduced as part as Java 8. This solution uses the approach of first creating a map to count the number of occurrences of each character. It then uses this map to find the first character which occurs only once. This runs in O(N) time.

下面的解决方案是一种优雅的方法，可以在一个字符串中找到第一个独特的字符，使用的新特性已经被引入到Java 8中。该解决方案使用第一个创建映射的方法来计算每个字符的出现次数。然后，它使用这张地图来寻找第一个只出现一次的字符。这是在O(N)时间内运行的。

import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;

import java.util.Arrays;
import java.util.List;
import java.util.Map;

// Runs in O(N) time and uses lambdas and the stream API from Java 8
//   Also, it is only three lines of code!
private static String findFirstUniqueCharacterPerformantWithLambda(String inputString) {
  // convert the input string into a list of characters
  final List<String> inputCharacters = Arrays.asList(inputString.split(""));

  // first, construct a map to count the number of occurrences of each character
  final Map<Object, Long> characterCounts = inputCharacters
    .stream()
    .collect(groupingBy(s -> s, counting()));

  // then, find the first unique character by consulting the count map
  return inputCharacters
    .stream()
    .filter(s -> characterCounts.get(s) == 1)
    .findFirst()
    .orElse(null);
}

#26

Here is one more solution with o(n) time complexity.

这是一个具有o(n)时间复杂度的解决方案。

public void findUnique(String string) {
    ArrayList<Character> uniqueList = new ArrayList<>();
    int[] chatArr = new int[128];
    for (int i = 0; i < string.length(); i++) {
        Character ch = string.charAt(i);
        if (chatArr[ch] != -1) {
            chatArr[ch] = -1;
            uniqueList.add(ch);
        } else {
            uniqueList.remove(ch);
        }
    }
    if (uniqueList.size() == 0) {
        System.out.println("No unique character found!");
    } else {
        System.out.println("First unique character is :" + uniqueList.get(0));
    }
}

#27

I read through the answers, but did not see any like mine, I think this answer is very simple and fast, am I wrong?

我通读了答案，但没有看到任何像我一样的答案，我觉得这个答案很简单也很快速，我错了吗?

def first_unique(s):
    repeated = []

    while s:
        if s[0] not in s[1:] and s[0] not in repeated:
            return s[0]
        else:
            repeated.append(s[0])
            s = s[1:]
    return None

test

(first_unique('abdcab') == 'd', first_unique('aabbccdad') == None, first_unique('') == None, first_unique('a') == 'a')

#28

Question : First Unique Character of a String This is the most simplest solution.

问题:字符串的第一个惟一字符是最简单的解决方案。

public class Test4 {
    public static void main(String[] args) {
        String a = "GiniGinaProtijayi";

        firstUniqCharindex(a);
    }

    public static void firstUniqCharindex(String a) {
        int[] count = new int[256];
        for (int i = 0; i < a.length(); i++) {
            count[a.charAt(i)]++;
        }
        int index = -1;
        for (int i = 0; i < a.length(); i++) {
            if (count[a.charAt(i)] == 1) {
                index = i;
                break;
            } // if
        }
        System.out.println(index);// output => 8
        System.out.println(a.charAt(index)); //output => P

    }// end1
}

IN Python :

在Python中:

def firstUniqChar(a):
  count = [0] * 256
  for i in a: count[ord(i)] += 1 
  element = ""
  for items in a:
      if(count[ord(items) ] == 1):
          element = items ;
          break
  return element


a = "GiniGinaProtijayi";
print(firstUniqChar(a)) # output is P

#29

how about using a suffix tree for this case... the first unrepeated character will be first character of longest suffix string with least depth in tree..

在这个例子中使用一个后缀树怎么样?第一个不重复的字符将是最长的后缀字符串的第一个字符，在树中有最小的深度。

#30

Create Two list -

创建了两个列表,

1. unique list - having only unique character .. UL
2. 唯一的列表-只有唯一的字符。UL
3. non-unique list - having only repeated character -NUL
4. 非唯一列表-只有重复字符- nul。

  for(char c in str) {
    if(nul.contains(c)){
     //do nothing
    }else if(ul.contains(c)){
      ul.remove(c);
      nul.add(c);
    }else{
       nul.add(c);
    }