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

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

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

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

寻找一个长度为3n的数组中出现次数超过n的元素
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;;
寻找一个长度为3n的数组中出现次数超过n的元素

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

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

上一篇:maven


下一篇:Linux redis安装