튜플의 더 큰 값을 반환합니다.

Question

목록의 모드를 찾고 해당 튜플을 목록에서 반환하려고 시도하고 있습니다.

fun counter(_, nil) = 0 
    | counter(a, x::xs) = if a = x then 1+counter(a, xs) 
      else counter(a, xs); 

fun countList(nil) = [] 
    | countList(x::xs) = 
    (x, counter(x, x::xs))::countList(xs); 

val lst = countList([1,2,1,1,3,4,5,2,1,2,1]); 

나에게 발 LST =를 [(부여, 나는 그것이 내가 각각의 번호는 그 이후에 발생 횟수의 목록을 반환 할 수있는 점에있다, 그러나 그것은 또한 나를 먼저 과거 발생 준다 (1,2,1), (2,3), (1,4), (1,3), (3,1), (4,1), (5,1), (2,2) : (int * int) 목록

각 값을 반복하여 첫 번째 값이 같고 만 있는지 확인하십시오. 첫 번째 가치를주고, 가장 큰 것을 돌려 주겠다.하지만 나는 그 부분을 이해할 수있을 것 같다. 목록을 통해 반복적으로 문제가 발생하여 현재 확인중인 값과 비교하는 중일 것입니다.

Answer 1

lst 목록을 계산 한 후에는 일치하는 요소를 찾을 필요가 없습니다. 당신이해야 할 유일한 일은 최대 튜플 두 번째 값을 가진 요소를 찾기 위해 목록을 탐색하는 것입니다.

fun findMax l = 
    let fun find (nil, acc) = acc 
    | find ((value, count)::xs, (acc_value, acc_count)) = 
    if count > acc_count then find (xs, (value, count)) 
    else if value = acc_value then (acc_value, acc_count) 
    else find (xs, (acc_value, acc_count)) 
    in find (l, (0, 0)) end; 

findMax lst; 
val it = (1, 5): int * int 

그러나,이 용액에 (N 2) O 복잡도를 갖는다. 또는 O (n * log n) 시간에 요소를 먼저 정렬 한 다음 최대 발생 횟수를 가진 목록에서 첫 번째 요소 (또는 여러 요소)를 반환 할 수 있습니다.