Первый неповторяющийся символ в строке? в хаскеле или F #

Question

Учитывая последовательность символов, каков наиболее эффективный способ найти первый неповторяющийся символ? Заинтересованы чисто функциональная реализация haskell или F #.

Answer 1

Достаточно простое использование Data.Set в сочетании с filter выполнит работу в эффективном однострочном режиме. Поскольку это кажется домашним заданием, я отказываюсь предоставить точную строку: -)

Сложность, как мне кажется, должна быть O (n log m), где m - количество различных символов в строке, а n - общее количество символов в строке.

Answer 2

Простое решение F #:

let f (s: string) =
  let n = Map(Seq.countBy id s)
  Seq.find (fun c -> n.[c] = 1) s

Answer 3

Альтернативное решение Haskell O (n log n) с использованием Data.Map и без сортировки:

module NonRepeat (
    firstNonRepeat
    )
    where

import Data.List (minimumBy)
import Data.Map (fromListWith, toList)
import Data.Ord (comparing)

data Occurance = Occ { first :: Int, count :: Int }
    deriving (Eq, Ord)

note :: Int -> a -> (a, Occurance)
note pos a = (a, Occ pos 1)

combine :: Occurance -> Occurance -> Occurance
combine (Occ p0 c0) (Occ p1 c1) = Occ (p0 `min` p1) (c0 + c1)

firstNonRepeat :: (Ord a) => [a] -> Maybe a
firstNonRepeat = fmap fst . findMinimum . occurances
    where occurances = toList . fromListWith combine . zipWith note [0..]
          findMinimum = safeMinimum . filter ((== 1).count.snd)
          safeMinimum [] = Nothing
          safeMinimum xs = Just $ minimumBy (comparing snd) xs

Answer 4

Вот решение F # в O(n log n): отсортировать массив, затем для каждого символа в исходном массиве выполнить его двоичный поиск в отсортированном массиве: если он единственный в своем роде, то все.

open System
open System.IO
open System.Collections.Generic

let Solve (str : string) =
    let arrStr = str.ToCharArray()
    let sorted = Array.sort arrStr
    let len = str.Length - 1

    let rec Inner i = 
        if i = len + 1 then
            '-'
        else
            let index = Array.BinarySearch(sorted, arrStr.[i])
            if index = 0 && sorted.[index+1] <> sorted.[index] then 
                arrStr.[i]
            elif index = len && sorted.[index-1] <> sorted.[index] then 
                arrStr.[i]
            elif index > 0 && index < len && 
                 sorted.[index+1] <> sorted.[index] && 
                 sorted.[index-1] <> sorted.[index] then 
                arrStr.[i]
            else
                Inner (i + 1)

    Inner 0

let _ =
    printfn "%c" (Solve "abcdefabcf")

A - означает, что все символы повторяются.

Редактировать: безобразный хак с использованием - для "нет решения", как вы можете использовать Опции , о которых я постоянно забываю! Упражнение для читателя, так как это выглядит как домашнее задание.

Answer 5

Вот немного длинное решение, но гарантированно будет наихудший O (n log n):

import List
import Data.Ord.comparing

sortPairs :: Ord a => [(a, b)]->[(a, b)]
sortPairs = sortBy (comparing fst)

index :: Integral b => [a] -> [(a, b)]
index = flip zip [1..]

dropRepeated :: Eq a => [(a, b)]->[(a, b)]
dropRepeated [] = []
dropRepeated [x] = [x]
dropRepeated (x:xs) | fst x == fst (head xs) =
                          dropRepeated $ dropWhile ((==(fst x)).fst) xs
                    | otherwise =
                          x:(dropRepeated xs)

nonRepeatedPairs :: Ord a => Integral b => [a]->[(a, b)]
nonRepeatedPairs = dropRepeated . sortPairs . index

firstNonRepeating :: Ord a => [a]->a
firstNonRepeating = fst . minimumBy (comparing snd) . nonRepeatedPairs

Идея состоит в том, чтобы: отсортировать строку лексикографически, чтобы можно было легко удалить любые повторяющиеся символы за линейное время и найти первый символ, который не повторяется. Но чтобы найти его, нам нужно сохранить информацию о позициях персонажей в тексте.

Скорость в простых случаях (например, [1..10000]) не идеальна, но для чего-то более сложного ([1..10000] ++ [1..10000] ++ [10001]) вы можете увидеть разницу между этим и наивным O (n ^ 2).

Конечно, это можно сделать за линейное время, если размер алфавита равен O (1), но кто знает, насколько велик алфавит ...

Answer 6

Это чистый C # (поэтому я предполагаю, что есть аналогичная версия F #), которая будет эффективна, если GroupBy эффективна (что и должно быть):

static char FstNonRepeatedChar(string s)
{
    return s.GroupBy(x => x).Where(xs => xs.Count() == 1).First().First();
}

Answer 7

Как насчет этого:

let firstNonRepeat s =
  let repeats = 
    ((Set.empty, Set.empty), s)
    ||> Seq.fold (fun (one,many) c -> Set.add c one, if Set.contains c one then Set.add c many else many)
    |> snd
  s
  |> Seq.tryFind (fun c -> not (Set.contains c repeats))

Answer 8

let firstNonRepeating (str:string) =
    let rec inner i cMap =
        if i = str.Length then
            cMap 
            |> Map.filter (fun c (count, index) -> count = 1) 
            |> Map.toSeq 
            |> Seq.minBy (fun (c, (count, index)) -> index)
            |> fst      
        else
            let c = str.[i]
            let value = if cMap.ContainsKey c then 
                            let (count, index) = cMap.[c]
                            (count + 1, index)
                        else 
                            (1, i)
            let cMap = cMap.Add(c, value)
            inner (i + 1) cMap 
    inner 0 (Map.empty)

Вот более простая версия, которая жертвует скоростью.

let firstNonRepeating (str:string) =
    let (c, count) = str 
                     |> Seq.countBy (fun c -> c) 
                     |> Seq.minBy (fun (c, count) -> count)
    if count = 1 then Some c else None