Это, вероятно, не самый красивый код, но вот с чем я пришел (F #). Сначала я преобразовываю каждый элемент в промежуточный формат. Этот формат содержит сам элемент, позицию его возникновения и сумму, в которой он произошел.
type T<'a> = {
Element: 'a
Position: int
Occurred: int
}
Идея состоит в том, что эти записи могут быть добавлены. Поэтому вы можете сначала преобразовать каждый элемент, а затем добавить их вместе. Таким образом, список как
[1;3]
будет первым преобразован в
[{Element=1;Position=0;Occurred=1}; {Element=3;Position=1;Occurred=1}]
Добавляя два вместе, вы только можете добавить их с тем же «Элемент». Позиция с меньшим номером из обоих взята, и Произошло только что добавлено вместе. Так что, если вы, например, иметь
{Element=3;Position=1;Occurred=2} {Element=3;Position=3;Occurred=2}
результат будет
{Element=3;Position=1;Occurred=4}
Идея, что я имел в виду, был Monoid. Но в реальном Моноиде вы должны были придумать, что вы также можете добавить разные элементы вместе. Попробовав какой-то материал, я чувствую, что ограничение просто добавления того же Элемента куда проще. Я создал небольшой модуль с типом. Включая некоторые вспомогательные функции для создания, добавления и сравнения.
module Occurred =
type T<'a> = {
Element: 'a
Position: int
Occurred: int
}
let create x pos occ = {Element=x; Position=pos; Occurred=occ}
let sameElements x y = x.Element = y.Element
let add x y =
if not <| sameElements x y then failwith "Cannot add two different Occurred"
create x.Element (min x.Position y.Position) (x.Occurred + y.Occurred)
let compareOccurredPosition x y =
let occ = compare x.Occurred y.Occurred
let pos = compare x.Position y.Position
match occ,pos with
| 0,x -> x * -1
| x,_ -> x
С этой настройкой я теперь написал две дополнительные функции. Одна функция aggregate
, которая сначала превращает каждый элемент в Occurred.T
, группирует их по x.Element
(результат - список). И затем он использует List.reduce
во внутреннем списке, чтобы добавить Связанный с тем же Элементом вместе. Результатом является список, который содержит только один Occurred.T
для каждого элемента с первой позицией и количеством отмеченных предметов.
let aggregate =
List.mapi (fun i x -> Occurred.create x i 1)
>> List.groupBy (fun occ -> occ.Element)
>> List.map (fun (x,occ) -> List.reduce Occurred.add occ)
Вы можете использовать эту функцию агрегата для реализации различной логики агрегации. В вашем случае вам нужен только тот, который имеет самые высокие места и самую низкую позицию. Я написал еще одну функцию, которая сделала это.
let firstMostOccurred =
List.sortWith (fun x y -> (Occurred.compareOccurredPosition x y) * -1) >> List.head >> (fun x -> x.Element)
1 примечание. Occurred.compareOccurredPosition
написано, что оно сортирует все в порядке возрастания. Я думаю, что люди ожидают, что в этом порядке по умолчанию будет доходить до самого маленького элемента. Таким образом, по умолчанию первым элементом будет элемент с наименьшим вхождением и самой большой позицией. Путем умножения результата на -1
вы превращаете эту функцию в нисходящую функцию сортировки. Причина, почему я сделал это, это то, что я мог бы использовать List.head
. Я также мог использовать List.last
, чтобы получить последний элемент, но я чувствовал, что лучше не переходить весь список снова, чтобы получить последний элемент. Кроме того, вам не нужен Occurred.T
, который вам нужен сам, поэтому я развожу Element
, чтобы получить номер.
Вот все в действии
let ll = [
[1;2;5;1;2;3;4;5;5;4;5;5]
[2;1;2;1;1;2]
[-1;2;1;2;5;-1;5;5;2]
[7]
]
ll
|> List.map aggregate
|> List.map firstMostOccurred
|> List.iter (printfn "%d")
Этот код теперь будет печатать
5
2
2
7
Это еще некоторые грубые края, как
Occurred.add
бросает исключение, если вы пытаетесь добавить Произошло с различными элементами
List.head
бросает исключение для пустых списков
И в обоих случаях код не написанными для обработки этих случаев или убедившись, что исключение не будет повышаться.
может возникнуть проблема в вашем коде: x :: mode l , так как режим l возвращает int, а не список. Думаю, вы должны поставить режим (x :: l). то же исправление на другой строке. –
Возможный дубликат [Min/Max и наиболее часто встречающийся элемент списка] (http://stackoverflow.com/questions/33529942/min-max-and-most-frequest-element-of-a-list) –