如何从字符串中找到第一个非重复字符?

I've spent half day trying to figure out this and finally I got working solution. However, I feel like this can be done in simpler way. I think this code is not really readable.

我花了半天的时间试图解决这个问题，终于找到了解决方案。然而，我觉得这可以用更简单的方式来完成。我认为这段代码不是真正可读的。

Problem: Find first non-repetitive character from a string.

问题:从字符串中查找第一个非重复字符。

$string = "abbcabz"

字符串美元= " abbcabz "

In this case, the function should output "c".

在这种情况下，函数应该输出“c”。

The reason I use concatenation instead of $input[index_to_remove] = '' in order to remove character from a given string is because if I do that, it actually just leave empty cell so that my return value $input[0] does not not return the character I want to return.

我使用串联而不是$input[index_to_remove] = "的原因是为了从给定的字符串中删除字符，因为如果我这样做，它实际上只留下空单元格，这样我的返回值$input[0]就不会返回我想要返回的字符。

For instance,

例如,

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

This will output "bc"

这将输出“公元前”

But actually if I test,

但是如果我测试，

var_dump($str);

it will give me:

它会给我:

string(3) "bc"

Here is my intention:

这是我的意愿:

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

Code:

代码:

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

8 个解决方案

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

#2

Python:

Python:

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

Same in PHP:

同样的在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];
 }
}

#3

Pseudocode:

伪代码:

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

Basically, you find all distinct letters in the string, and for each letter, you associate it with a count of how many of that letter exist in the string. then you return the first one that has a count of 1

基本上，你在字符串中找到所有不同的字母，对于每个字母，你将它与字符串中有多少个字母联系起来。然后返回第一个计数为1的

The complexity of this method is O(n^2) in the worst case if using arrays. You can use an associative array to increase it's performance.

该方法的复杂度是O(n ^ 2)在最坏的情况下如果使用数组。可以使用关联数组来提高性能。

#4

1- use a sorting algotithm like mergesort (or quicksort has better performance with small inputs)
2- then control repetetive characters

1-使用排序算法，如归并排序(或快速排序在小输入下有更好的性能)2-然后控制重复字符

• non repetetive characters will be single
  
• 非重复字符将是单字符
• repetetvives will fallow each other
  
• 中继生物将彼此休耕

Performance : sort + compare
Performance : O(n log n) + O(n) = O(n log n)
For example

性能:排序+比较性能:例如O(n log n) + O(n) = O(n log n)

    $string = "abbcabz"

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

Then take first char form string then compare with next one if match repetetive
move to the next different character and compare
first non-matching character is non-repetetive

然后取第一个字符形式的字符串，然后与下一个字符进行比较，如果匹配下一个不同的字符，则比较第一个不匹配的字符为非重复字符

#5

This can be done in much more readable code using some standard PHP functions:

这可以通过使用一些标准的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;

#6

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

#7

This should replace your code...

这将替换您的代码……

$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));

Edit: spoke too soon. Took out 'array_unique', thought it actually dropped duplicate values. But character order should be preserved to be able to find the first character.

编辑:言之过早。取出“array_unique”，认为它实际上放弃了重复的值。但是字符顺序应该保留，以便能够找到第一个字符。

#8

Here's a function in Scala that would do it:

下面是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: Option[Char] = Some(c)

scala> firstUnique(“abbcabz”.toList) res5:选项[Char] = Some(c)

And here's the equivalent in 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"

*主要> firstUnique“abbcabz”

Just 'c'

只是“c”

You can solve this more generally by abstracting over lists of things that can be compared for equality:

你可以通过抽象出一系列可以比较平等的东西来更普遍地解决这个问题:

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

Strings are just one such list.

字符串就是这样的一个列表。