Как найти первый неповторяющийся символ из строки?

Question

Я потратил полдня, пытаясь выяснить это, и, наконец, я получил рабочее решение.Однако я чувствую, что это можно сделать проще.Я думаю, что этот код на самом деле не читабелен.

Проблема: Найти первый неповторяющийся символ из строки.

$ string = "abbcabz"

В этом случаефункция должна вывести «c».

Причина, по которой я использую конкатенацию вместо $input[index_to_remove] = '' для удаления символа из заданной строки, заключается в том, что если я это сделаю, то на самом деле просто оставлю пустую ячейку, так что мое возвращаемое значение$ input [0] не возвращает символ, который я хочу вернуть.

Например,

$str = "abc";
$str[0] = '';
echo $str;

Это выведет "bc"

Но на самом деле, если ятест,

var_dump($str);

это даст мне:

string(3) "bc"

Вот мое намерение:

Given: input

while first char exists in substring of input {
  get index_to_remove
  input = chars left of index_to_remove . chars right of index_to_remove

  if dupe of first char is not found from substring
     remove first char from input 
}
return first char of input

Код:

function find_first_non_repetitive2($input) {

    while(strpos(substr($input, 1), $input[0]) !== false) {

        $index_to_remove = strpos(substr($input,1), $input[0]) + 1;
        $input = substr($input, 0, $index_to_remove) . substr($input, $index_to_remove + 1);

        if(strpos(substr($input, 1), $input[0]) == false) {
            $input = substr($input, 1);     
        }
    }
    return $input[0];
}

Answer 1

<?php
    // In an array mapped character to frequency, 
    // find the first character with frequency 1.
    echo array_search(1, array_count_values(str_split('abbcabz')));

Answer 2

Python:

def first_non_repeating(s):
 for i, c in enumerate(s):
  if s.find(c, i+1) < 0:
   return c
 return None

То же в PHP:

function find_first_non_repetitive($s)
{
 for($i = 0; i < strlen($s); i++) {
  if (strpos($s, $s[i], i+1) === FALSE)
   return $s[i];
 }
}

Answer 3

Это должно заменить ваш код ...

$array = str_split($string);
$array = array_count_values($array);
$array = array_filter($array, create_function('$key,$val', 'return($val == 1);'));
$first_non_repeated_letter = key(array_shift($array));

Редактировать: говорил слишком рано. Вытащил 'array_unique', подумал, что на самом деле отбрасывает повторяющиеся значения Но порядок символов должен быть сохранен, чтобы можно было найти первый символ.

Answer 4

$str="abbcade";
$checked= array(); // we will store all checked characters in this array, so we do not have to check them again

for($i=0; $i<strlen($str); $i++)
{
    $c=0;
    if(in_array($str[$i],$checked)) continue;

    $checked[]=$str[$i];

    for($j=$i+1;$j<=strlen($str);$j++)
    {
        if($str[$i]==$str[$j]) 
        {
            $c=1;
            break;  
        }
    }
    if($c!=1) 
    {
        echo "First non repetive char is:".$str[$i]; 
        break;
    }
}

Answer 5

Вот функция в Scala, которая сделает это:

def firstUnique(chars:List[Char]):Option[Char] = chars match { 
  case Nil => None
  case head::tail => {
    val filtered = tail filter (_!=head)
    if (tail.length == filtered.length) Some(head) else firstUnique(filtered)
  }
}

scala> firstUnique ("abbcabz" .toList)
res5: опция [Char] = Some (c)

А вот эквивалент в Haskell:

firstUnique :: [Char] -> Maybe Char
firstUnique [] = Nothing
firstUnique (head:tail) = let filtered = (filter (/= head) tail) in
            if (tail == filtered) then (Just head) else (firstUnique filtered)

* Main> firstUnique "abbcabz"

Просто 'c'

Вы можете решить эту проблему более широко, абстрагируясь от списков вещей, которые можно сравнить на равенство:

firstUnique :: Eq a => [a] -> Maybe a

Строки - это только один из таких списков.

Answer 6

1 - используйте алгоритм сортировки, такой как mergesort (или быстрая сортировка имеет лучшую производительность при небольших входах)
2- затем управляйте повторяющимися символами

• неповторяющиеся символы будут одиночными
  
• повторители будут сменять друг друга
  

Производительность: сортировка + сравнение
Производительность: O (n log n) + O (n) = O (n log n)
Например

    $string = "abbcabz"

    $string = mergesort ($string)
    // $string = "aabbbcz" 

Затем возьмите первую строку формы символа, а затем сравните со следующей, если она повторяется
перейти к следующему другому персонажу и сравнить
первый несовпадающий символ не повторяется

Answer 7

Это можно сделать в гораздо более удобочитаемом коде, используя некоторые стандартные функции PHP:

// Count number of occurrences for every character
$counts = count_chars($string);

// Keep only unique ones (yes, we use this ugly pre-PHP-5.3 syntax here, but I can live with that)
$counts = array_filter($counts, create_function('$n', 'return $n == 1;'));

// Convert to a list, then to a string containing every unique character
$chars = array_map('chr', array_keys($counts));
$chars = implode($chars);

// Get a string starting from the any of the characters found
// This "strpbrk" is probably the most cryptic part of this code
$substring = strlen($chars) ? strpbrk($string, $chars) : '';

// Get the first character from the new string
$char = strlen($substring) ? $substring[0] : '';

// PROFIT!
echo $char;

Answer 8

псевдокод:

Array N;

For each letter in string
  if letter not exists in array N
    Add letter to array and set its count to 1
  else
    go to its position in array and increment its count
End for

for each position in array N
  if value at potition == 1
    return the letter at position and exit for loop
  else
    //do nothing (for clarity)
end for

По сути, вы находите все отдельные буквы в строке, и для каждой буквы вы связываете ее со счетчиком количества этих букв в строке. затем вы возвращаете первый, который имеет счет 1

Сложность этого метода - O (n ^ 2) в худшем случае, если используются массивы. Вы можете использовать ассоциативный массив для увеличения его производительности.

Answer 9

Также можно сделать, используя array_key_exists во время построения ассоциативного array из string. Каждый символ будет ключом и будет считать число как значение.

$sample = "abbcabz";

$check = [];
for($i=0; $i<strlen($sample); $i++)
{
    if(!array_key_exists($sample[$i], $check))
    {
        $check[$sample[$i]] = 1;
    }
    else
    {
        $check[$sample[$i]] += 1;
    }
}

echo array_search(1, $check);