在string中查找第一个未重复的字符

find只出现在string中的第一个字符的最快方法是什么？

Answer 1

在处理整个string之前，你不能知道这个字符是不重复的，所以我的build议是这样的：

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 

编辑：最初张贴的代码是坏的，但这个最新的片段是瑞安的电脑™authentication工作。

Answer 2

它必须至less是O（n），因为你不知道一个字符是否会重复，直到你读完所有的字符。

所以你可以遍历字符，并在第一次看到它的时候把每个字符追加到列表中，并且分别logging你看过的次数（事实上，对于count来说唯一的值是“0” ，“1”或“多于1”）。

当你到达string的末尾时，你只需要find列表中的第一个字符，它的数目只有一个。

---

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 

这在O（n）中运行。

Answer 3

为什么不使用基于堆的数据结构，如最小优先级队列。 在读取string中的每个字符时，根据string中的位置和发生次数将其添加到队列中。 您可以修改队列以在冲突中添加优先级，以便字符的优先级是该字符的数字外观的总和。 在循环结束时，队列中的第一个元素将是string中最不频繁的字符，如果有多个字符count = 1，则第一个元素是添加到队列中的第一个唯一字符。

Answer 4

这是另一个有趣的方法来做到这一点。 计数器需要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' 

Answer 5

许多答案正在尝试O（n），但忘记了插入和删除它们用于跟踪的列表/关联数组/集的实际成本。

如果你可以假设一个字符是一个字节，那么你使用一个由char索引的简单数组，并在其中保留一个计数。 这是真正的O（n）因为数组访问保证O（1），最后通过数组来查找第一个元素与1是恒定的时间（因为该数组有一个小的，固定的大小）。

如果你不能假设一个字符是一个字节，那么我会build议对这个string进行sorting，然后检查相邻的值。 这将是O（n log n）的sorting加上O（n）的最后一关。 所以它是有效的O（n log n），这比O（n ^ 2）好。 此外，它几乎没有空间开销，这是尝试O（n）的许多答案的另一个问题。

Answer 6

计数器需要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' 

Answer 7

重构先前提出的解决scheme（不必使用额外的列表/内存）。 这超过了string两次。 所以这也需要O（n）像原来的解决scheme。

 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 

Answer 8

以下是查找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') 

这里是一个相同样式函数的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?')); 

在这两种情况下，我都使用了一个计数器，知道如果字符在string中的任何位置都不匹配，它只会出现在string中，所以我只是把它计算在内。

Answer 9

我认为这应该在C中进行。这在O（n）时间内操作，对于插入和删除操作符的顺序没有歧义。 这是一种计数sorting（桶sorting的最简单forms，本身就是基数sorting的简单forms）。

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

Answer 10

在Ruby中：

（原文：Andrew A. Smith）

 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" 

Answer 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 

Answer 12

其他JavaScript解决scheme是相当c风格的解决scheme，这里是一个更多的JavaScript风格的解决scheme。

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

Answer 13

在C中，这几乎是Shlemiel画家的algorithm （不完全是O（n！）而是大于0（n2））。

但是，对于合理大小的string，将会比“更好”的algorithm更好，因为O太小了。 这也可以很容易地告诉你第一个非重复string的位置。

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

编辑：这段代码假设你不是指连续的重复字符。

Answer 14

下面是Perl中的一个实现（version> = 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"; } } 

将此代码存储在一个脚本（我将其命名为non_repeated.pl ）中，并在less量input上运行该代码，可生成：

 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. 

Answer 15

这里是一个可能的解决scheme在ruby没有使用Array#detect （如在这个答案 ）。 使用Array#detect使得它太简单了，我想。

 ALPHABET = %w(abcdefghijklmnopqrstu vwxyz) 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 

似乎适用于一些简单的例子：

 fnr "abcdabcegghh" # => "d" fnr "abababababababaqababa" => "q" 

build议和更正非常感谢！

Answer 16

试试这个代码：

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

Answer 17

在Mathematica中，可以这样写：

 string = "conservationist deliberately treasures analytical"; Cases[Gather @ Characters @ string, {_}, 1, 1][[1]] 

 {"v"} 

Answer 18

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" 

Answer 19

这里有不同的做法 扫描string中的每个元素，并创build一个计数数组，存储每个元素的重复计数。 下次再次从数组中的第一个元素开始，打印第一个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; } 

Answer 20

input是= 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]; } 

Answer 21

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

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

Answer 22

function：

这个c＃函数使用了一个HashTable（Dictionary）并且具有O（2n）的最坏情况。

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

例：

string aword =“TEETER”;

Console.WriteLine（FirstNoRepeatingCharacter（AW​​ORD））; // print：R

Answer 23

我有两个string，即“独特”和“重复”。 每个angular色首次出现，被添加到“独特”。 如果第二次重复，则将其从“唯一”中删除并添加到“重复”中。 这样，我们将始终有一个独特的string在“独特”。 复杂性大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)); } 

Answer 24

下面的代码是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(); } } } } 

Answer 25

下面的解决scheme是一个很好的方法，它使用作为Java 8一部分引入的新function在string中查找第一个唯一字符。此解决scheme使用首先创build映射来计算每个字符出现次数的方法。 然后它使用这个映射来查找只出现一次的第一个字符。 这运行在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); } 

Answer 26

这是一个更复杂的解决schemeo（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)); } } 

Answer 27

我通过答案阅读，但没有看到任何像我的，我想这个答案是非常简单和快速，我错了吗？

 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 

testing

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

Answer 28

在这种情况下如何使用后缀树…第一个不重复的字符将是树中最小深度的最长后缀string的第一个字符。

Answer 29

创build两个列表 –

1. 唯一的名单 – 只有唯一的字符.. UL
2. 非唯一列表 – 只有重复的字符-NUL

   for（char c in str）{
    如果（nul.contains（C））{
      //没做什么
     } else if（ul.contains（c））{
       ul.remove（C）;
       nul.add（C）;
     }其他{
        nul.add（C）;
     }

Answer 30

 Another answer(Might not be so efficient but a kind of approach that we can try in c++; Time complexity:O(n) Space complexity:O(n)). char FirstNotRepeatingCharInString(char *str) { //Lets assume a set to insert chars of string char result; multiset<char> st; for(int i=0;i<strlen(str);i++) { st.insert(str[i]); } for(int i=0;i<strlen(str);i++) { if(st.count(str[i]) <=1){ result = str[i]; break; } } return result; }