寻找一个长度为3n的数组中出现次数超过n的元素

思路1: 排序，然后扫描一遍，这样的复杂度主要在于排序，时间复杂度为O(n log n)

思路2: 可以借用快速排序的思想，先用O(n)的时间找到n/3位置的元素，再用O(n)的时间找到2n/3位置的元素，出现次数超过n次的元素是这两个中的一个，扫描一边统计一下次数就完成了。

思路3: 每次删掉3个不同的元素，保留两个不同的元素以及他们出现的频率，最后两个元素中，频率高的元素既是所求。下面是ocaml的代码

let find lst =
  let rec find_int c1 v1 c2 v2 l =
    match l with
     [] -> if c1 > c2 then v1 else v2
    | h::rest -> if h = v1 then find_int (c1+1) v1 c2 v2 rest
                 else if h = v2 then find_int c1 v1 (c2+1) v2 rest
                 else if c1 = 0 then find_int 1  h  c2 v2 rest
                 else if c2 = 0 then find_int c1 v1 1 h rest
                 else find_int (c1-1) v1 (c2-1) v2 rest
  in
find_int 0 2 0 1 lst;;

这里使用了尾递归的方法来实现，有点是扫描一遍就可以找出来，而且原来数组不需要改动，同时时间复杂度保持在O(n)