Найти первый неповторенный символ в строке

Question

Какой самый быстрый способ найти первый символ, который появляется в строке только один раз?

Answer 1

Другие решения 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];

}

Answer 2

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 3

Другой подход здесь.просканируйте каждый элемент в строке и создайте массив 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;    
} 

Answer 4

Я прочитал ответы, но не увидел ничего похожего на мой, думаю, этот ответ очень простой и быстрый, я не прав?

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')

Answer 5

Следующее решение представляет собой элегантный способ поиска первого уникального символа в строке с использованием новых функций, которые были представлены как часть 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);
}

Answer 6

У меня есть две строки, то есть «уникальная» и «повторная». Каждый персонаж, появляющийся в первый раз, добавляется к «уникальному». Если оно повторяется во второй раз, оно удаляется из «уникального» и добавляется в «повторное». Таким образом, у нас всегда будет строка уникальных символов в «уникальном». Сложность большая 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 7

Попробуйте этот код:

    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 8

Ниже приведено решение в C ++:

 char FirstNotRepeatingChar(char* pString)
 {
     if(pString == NULL)
         return '\0';

     const int tableSize = 256;
     unsigned int hashTable[tableSize];
     for(unsigned int i = 0; i<tableSize; ++ i)
         hashTable[i] = 0;

     char* pHashKey = pString;
     while(*(pHashKey) != '\0')
         hashTable[*(pHashKey++)] ++;

     pHashKey = pString;
     while(*pHashKey != '\0')
     {
         if(hashTable[*pHashKey] == 1)
             return *pHashKey;

         pHashKey++;
     }

     return '\0';
 }

У меня был блог для обсуждения этой проблемы на http://codercareer.blogspot.com/2011/10/no-13-first-character-appearing-only.html. Любые комментарии будут искренне оценены.

Answer 9

Вот возможное решение в ruby ​​без использования 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"

Предложения и исправления очень приветствуются!

Answer 10

Вот реализация в 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";
  }
}

Хранение этого кода в скрипте (который я назвал 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.