Я потратил полдня, пытаясь понять это, и, наконец, у меня появилось рабочее решение. Тем не менее, я чувствую, что это можно сделать проще. Я думаю, что этот код на самом деле не читается.
Проблема: найдите первый неповторяющийся символ из строки.
$ 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]; }
<?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')));
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]; } }
псевдокод:
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) в худшем случае при использовании массивов. Вы можете использовать ассоциативный массив для повышения его производительности.
1- используйте сортировку algotithm like mergesort (или quicksort имеет лучшую производительность с небольшими входами)
2- затем управлять повторяющимися символами
- не повторяющиеся символы будут одиночными
- повторения будут парить друг друга
Производительность: сортировка + сравнение
Производительность: O (n log n) + O (n) = O (n log n)
Например
$string = "abbcabz" $string = mergesort ($string) // $string = "aabbbcz"
Затем возьмите первую строку формы char, затем сравните ее со следующей, если совпадение повторяется
перейдите к следующему другому символу и сравните
первый несогласованный символ не повторяется
Это можно сделать в гораздо более читаемом коде, используя некоторые стандартные функции 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;
$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; } }
Это должно заменить ваш код …
$ 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», подумал, что он фактически сбросил повторяющиеся значения. Но порядок символов должен быть сохранен, чтобы найти первого персонажа.
Вот функция в 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] = Некоторые (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)
* Главная> firstUnique "abbcabz"
Просто 'c'
Вы можете решить это в целом путем абстрагирования списков вещей, которые можно сравнить для равенства:
firstUnique :: Eq a => [a] -> Maybe a
Строки – всего лишь один такой список.