列表中元素的位置(OCaml)

Question

在OCaml中获取元素列表中元素位置的最快方法是什么？我知道如何在列表中获取元素的"第n"位置,但我想知道如果我已经知道该值,如何获取该元素的位置.

Answer 1

我相信最快的方式是最常用的方式:

1. 扫描列表
2. 如果你点击了所需的元素,则返回位置
3. 如果从未打过,那么这是最糟糕的情况,扫描整个列表.

时间复杂度为O(N)

let index_of e l = 
  let rec index_rec i = function
    | [] -> raise Not_found
    | hd::tl -> if hd = e then i else index_rec (i+1) tl
  in
  index_rec 0 l