如何從字符串中找到第一個不重複的字符？

Question

我花了半天的時間試圖弄清楚這一點，最後我得到了工作解決方案。 但是，我覺得這可以用更簡單的方式完成。 我認爲這段代碼不是真正可讀的。

問題：從字符串中查找第一個不重複的字符。

$字符串= 「abbcabz」

在這種情況下，該函數應該輸出 「C」。

我使用並置而不是$input[index_to_remove] = '' 爲了從給定的字符串 刪除字符的原因是因爲如果我這樣做，它實際上只是留出空白單元格，這樣我 返回值$輸入[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

僞代碼：

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）。您可以使用關聯數組來提高其性能。

// 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 3

這可以在更可讀代碼使用一些標準的PHP函數來完成的repetetive字符

• 非的repetetive字符將是單
  
• 個repetetvives將休耕彼此
  

性能：排序+比較
性能：爲O（n log n）的+ O（n）的= O（N log n）的
例如

$string = "abbcabz" 

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

然後取第一個字符格式的字符串，然後用下一個比賽，如果
的repetetive移動 到下一個比較迪fferent性格和比較
第一個非匹配字符非的repetetive

Answer 4

1-使用排序algotithm像歸併（或快速排序具有小輸入更好的性能）
2-然後控制：

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

斯卡拉> firstUnique（ 「abbcabz」 .toList）
res5：選項[字符] =一些（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 

字符串是隻有一個這樣的名單。

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

Answer 7

這應該更換你的代碼...

 

$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 8

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