Каков самый быстрый способ найти первый символ, который появляется только один раз в строке?
Найти первый повторный символ в строке
Ответ 1
Вы не можете знать, что символ не повторяется до тех пор, пока вы не обработаете всю строку, поэтому мое предложение будет следующим:
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
Изменить: первоначально опубликованный код был плохим, но этот последний фрагмент сертифицирован для работы на Ryan Computer ™.
Ответ 2
Он должен быть как минимум O (n), потому что вы не знаете, будет ли символ повторяться, пока вы не прочитаете все символы.
Таким образом, вы можете перебирать символы и добавлять каждый символ в список при первом просмотре и отдельно подсчитывать, сколько раз вы его видели (на самом деле единственные значения, которые важны для подсчета, "0", "1" или "больше 1" ).
Когда вы дойдете до конца строки, вам просто нужно найти первый символ в списке, который имеет счетчик ровно один.
Пример кода в 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).
Ответ 3
Почему бы не использовать структуру данных на основе кучи, такую как очередь с минимальным приоритетом. Когда вы читаете каждый символ из строки, добавьте его в очередь с приоритетом, основанным на местоположении в строке и количестве вхождений до сих пор. Вы можете изменить очередь, чтобы добавить приоритеты при столкновении, чтобы приоритет символа был суммой чисел появления этого символа. В конце цикла первый элемент в очереди будет наименее частым символом в строке, и если есть несколько символов с count == 1, первым элементом был первый уникальный символ, добавленный в очередь.
Ответ 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'
Ответ 5
Многие ответы пытаются использовать O (n), но забывают о фактических расходах на вставку и удаление из списков/ассоциативных массивов/наборов, которые они используют для отслеживания.
Если вы можете предположить, что char - это один байт, вы используете простой массив, индексированный char, и держите в нем счет. Это действительно O (n), потому что доступ к массиву гарантирован O (1), а окончательный проход по массиву для поиска первого элемента с 1 - это постоянное время (потому что массив имеет небольшой фиксированный размер).
Если вы не можете предположить, что char - это один байт, я бы предложил сортировать строку и затем выполнить один проход, проверяя смежные значения. Это будет O (n log n) для сортировки плюс O (n) для окончательного прохода. Таким образом, это эффективно O (n log n), что лучше, чем O (n ^ 2). Кроме того, у него практически нет накладных расходов, что является еще одной проблемой со многими ответами, которые пытаются выполнить O (n).
Ответ 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'
Ответ 7
Я думаю, что это нужно делать в C. Это работает в O (n) времени без какой-либо двусмысленности относительно порядка операторов вставки и удаления. Это сортировка (простейшая форма сортировки в виде ведра, которая сама по себе является простой формой сортировки).
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;
}
Ответ 8
Рефакторинг решения, предложенного ранее (без использования дополнительного списка/памяти). Это проходит через строку дважды. Таким образом, это делает O (n) слишком похожим на исходное решение.
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
Ответ 9
Ниже приведена реализация 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 той же функции стиля 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?'));
В обоих случаях я использовал счетчик, зная, что если буква не сопоставляется нигде в строке, она будет встречаться только в строке один раз, поэтому я просто подсчитаю ее появление.
Ответ 10
В Ruby:
(Оригинальный кредит: Андрей А. Смит)
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
Другие решения для 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
в C, это почти Shlemiel the Painter Algorithm (не совсем O (n!), но больше 0 (n2)).
Но превзойдет "лучшие" алгоритмы для строк с разумным размером, потому что 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: этот код предполагает, что вы не имеете в виду последовательные повторяющиеся символы.
Ответ 14
Здесь реализована реализация в 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 [email protected]_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";
}
}
Сохранение этого кода в script (который я назвал non_repeated.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
Здесь возможно решение в рубине без использования Array#detect (как в этом ответе). Использование Array#detect делает это слишком легким, я думаю.
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
Кажется, нужно работать для некоторых простых примеров:
fnr "abcdabcegghh"
# => "d"
fnr "abababababababaqababa"
=> "q"
Предложения и исправления очень ценятся!
Ответ 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();
}
Ответ 17
В Mathematica можно написать следующее:
string = "conservationist deliberately treasures analytical";
Cases[Gather @ Characters @ string, {_}, 1, 1][[1]]
{"v"}
Ответ 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"
Ответ 19
Здесь различный подход. сканирование каждого элемента в строке и создание массива count, который хранит количество повторений каждого элемента. В следующий раз снова начните с первого элемента массива и напечатайте первое вхождение элемента с 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 = выход 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
Следующий код находится в С# со сложностью 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();
}
}
}
}
Ответ 22
Вот еще один подход... у нас может быть массив, который будет хранить счетчик и индекс первого вхождения символа. После заполнения массива мы могли бы jst пересечь массив и найти MINIMUM индекс, чей счет равен 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;
}
Ответ 23
Функции:
Эта функция С# использует HashTable (Словарь) и имеет наивысшую производительность 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";
еЫп (FirstNoRepeatingCharacter (aword));//print: R
Ответ 24
У меня две строки, то есть "уникальные" и "повторяющиеся". Каждый персонаж, появляющийся впервые, добавляется к "уникальному". Если он повторяется во второй раз, он удаляется из "уникального" и добавляется к "повторенному". Таким образом, мы всегда будем иметь строку уникальных символов в "unique". Сложность big 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));
}
Ответ 25
Следующее решение - это элегантный способ поиска первого уникального символа в строке с использованием новых функций, которые были введены как часть 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
Вот еще одно решение с временной сложностью 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
Я прочитал ответы, но не видел таких, как мой, я думаю, что этот ответ очень прост и быстр, я ошибаюсь?
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
Тест
(first_unique('abdcab') == 'd', first_unique('aabbccdad') == None, first_unique('') == None, first_unique('a') == 'a')
Ответ 28
Вопрос: первый уникальный символ строки Это самое простое решение.
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
}
В 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
Используя Java 8:
public class Test2 {
public static void main(String[] args) {
String a = "GiniGinaProtijayi";
Map<Character, Long> map = a.chars()
.mapToObj(
ch -> Character.valueOf((char) ch)
).collect(
Collectors.groupingBy(
Function.identity(),
LinkedHashMap::new,
Collectors.counting()));
System.out.println("MAP => " + map);
// {G=2, i=5, n=2, a=2, P=1, r=1, o=1, t=1, j=1, y=1}
Character chh = map
.entrySet()
.stream()
.filter(entry -> entry.getValue() == 1L)
.map(entry -> entry.getKey())
.findFirst()
.get();
System.out.println("First Non Repeating Character => " + chh);// P
}// main
}
Ответ 29
как насчет использования дерева суффиксов для этого случая... первый неповторяющийся символ будет первым символом самой длинной строки суффикса с наименьшей глубиной в дереве.
Ответ 30
Создать два списка -
- уникальный список - имеющий только уникальный символ. UL
- неуникальный список - имеющий только повторяющийся символ -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);
}