Làm cách nào để tìm ký tự không lặp lại đầu tiên từ một chuỗi?

Question

Tôi đã dành nửa ngày cố gắng tìm ra điều này và cuối cùng tôi đã nhận được giải pháp làm việc. Tuy nhiên, tôi cảm thấy như thế này có thể được thực hiện theo cách đơn giản hơn. Tôi nghĩ rằng mã này không thực sự dễ đọc.

Sự cố: Tìm ký tự không lặp lại đầu tiên từ chuỗi.

$ string = "abbcabz"

Trong trường hợp này, hàm sẽ xuất "c".

Lý do tôi sử dụng nối thay vì $input[index_to_remove] = '' để loại bỏ ký tự từ một chuỗi cho trước là bởi vì nếu tôi làm điều đó, nó thực sự chỉ để lại ô trống để trở lại giá trị $ đầu vào của tôi [0] không không trả lại ký tự tôi muốn trả lại.

Ví dụ,

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

chí đầu ra này "bc"

Nhưng trên thực tế nếu tôi thử nghiệm,

var_dump($str); 

nó sẽ cho tôi:

string(3) "bc" 

đây là ý định của tôi:

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

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

Mã giả:

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 

Về cơ bản, bạn tìm thấy tất cả các chữ khác nhau trong chuỗi, và cho mỗi chữ cái, bạn kết hợp nó với một đếm có bao nhiêu của lá thư đó tồn tại trong chuỗi. sau đó bạn trả lại số đầu tiên có số lượng 1

Độ phức tạp của phương pháp này là O (n^2) trong trường hợp xấu nhất nếu sử dụng mảng. Bạn có thể sử dụng mảng kết hợp để tăng hiệu suất của nó.

Answer 3

này có thể được thực hiện trong có thể đọc được nhiều hơn nữa mã sử dụng một số chức năng PHP tiêu chuẩn:

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

1- sử dụng một sắp xếp algotithm như mergesort (hoặc quicksort có hiệu suất tốt hơn với sự đóng góp nhỏ)
2- sau đó kiểm soát nhân vật repetetive

• phi nhân vật repetetive sẽ đơn
  
• repetetvives sẽ hoang mỗi Performance
  

khác: loại + so sánh
Hiệu suất: O (n log n) + O (n) = O (n log n)
Ví dụ

$string = "abbcabz" 

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

sau đó lấy đầu chuỗi dạng char sau đó so sánh với một tiếp theo nếu trận đấu repetetive
di chuyển đến di tiếp theo nhân vật fferent và so sánh
đầu tiên nhân vật không phù hợp là không repetetive

Answer 5

Dưới đây là một chức năng trong Scala rằng sẽ làm điều đó:

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: Lựa chọn [Char] = Một số (c)

Và đây là tương đương trong 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"

Chỉ cần 'c'

Bạn có thể giải quyết việc này tổng quát hơn bằng cách trừu tượng trên danh sách những thứ có thể được so sánh với bình đẳng:

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

Strings là chỉ một danh sách như vậy.

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

này nên thay thế mã của bạn ...

 

$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: nói quá sớm. Đã tìm ra 'array_unique', nghĩ rằng nó thực sự làm giảm giá trị trùng lặp. Nhưng thứ tự ký tự nên được giữ nguyên để có thể tìm thấy ký tự đầu tiên.

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 

Cùng trong 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]; 
} 
}