1

这是一个面试问题：

找到可以由给定数字的相同数字组成的下一个最大数字..

输入：4765，输出：5467

如果使用array，这并不难。

  1. 我们将数字转换为数字数组。
  2. x我们扫描数组，记录下一个邻居更大的最新（最低位置）数字（比如 as ）
  3. 如果下一个邻居更小（这意味着它正在下降），那么我们记录大于 x 的最小数字（比如 as y）
  4. 最后，我们交换 x 和 y

但是，在 OCaml 中，如果我们使用list，那么我不知道该怎么做。似乎该算法使递归变得困难。

有什么建议么？

编辑：

请注意我希望有一种实用的方式（使用list）

编辑

按照@comingstorm 的建议，我是这样实现的：

exception NotFound;;


let rev_list_of_int n = 
  let rec process n = 
    let x = n / 10 and y = n mod 10 
    in 
    if x = 0 && y = 0 then []
    else 
      y::(process x)
  in 
  process n;;

let find_next_by_list n =
  let l = rev_list_of_int n
  in
  let rec find_x before_x x after_x = 
    match after_x with
    | [] | _::[] -> (before_x, -1, after_x)
    | hd1::hd2::tl -> 
      if hd1 > hd2 then (hd1::before_x, hd2, tl)
      else find_x (hd1::before_x) x (hd2::tl)
  in 
  let (bx, x, ax) = find_x [] (-1) l (* ax is rev *)
  in 
  if x = -1 then raise NotFound
  else 
    let rec find_y x path = function
    | [] -> raise NotFound
    | hd::tl -> 
      if hd > x then (path, hd, tl)
      else find_y x (hd::path) tl
    in 
    let (left, y, right) = find_y x [] (List.rev bx) (* left is rev, right is not  *)
    in 
    (* rev ax, then y, then right, then x, then rev left*)
    (List.rev_append (y::ax) right) @ (x::List.rev left)
4

3 回答 3

2

为了以一种功能性的方式实现这一点，以相反的顺序维护您的数字列表会更有效 - 以便最快速变化的数字更接近列表的头部。这允许实现避免重新分配整个列表，从而提高摊销性能。

给定一个反向列表digits（从最不重要到最重要）：

Starting at the least-significant digit (the head of the reversed list):
  look for the first digit smaller than its predecessor:  call it "a_k"
  save the list of digits after a_k as:  "unchanged"
Starting again at the least-significant digit:
  look for the first digit larger than a_k:  call it "a_l"
Accumulate the output list functional-style, starting with "unchanged":
  add a_l to the head of the list
  starting a third time at the least-significant digit:
    add each digit to the head of the output (reversing that portion of the list)
      stopping before a_l
    add a_k to the head of the output, instead of a_l
    after skipping a_l, continue to add digits from original to output
      stopping before a_k

简而言之：要做到功能风格，您必须在适当的位置构建列表的“修改”交换/反转部分。您不必以最低有效数字优先顺序（如上述伪代码所假设的那样）维护您的列表，但如果您这样做，您的next_permutation函数将在时间和分配内存方面具有 O(1) 的摊销性能。

[编辑：更正，O(1) 性能仅在所有数字不同时...]

如果您确实想以最高有效数字优先的顺序维护您的数字，您仍然需要对交换/反向区域进行类似的扫描和重建，然后是未更改区域的有序副本。

于 2013-03-25T18:29:48.247 回答
1

只需按字典顺序生成下一个排列：

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
Swap a[k] with a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

在维基百科上找到。可以在这里找到 OCaml 中的实现：

The following Ocaml code implements a variation on this algorithm (it returns the permutations of 1..n in reverse reverse-lexicographic order) :

(* exchange into l @ [x] @ accu x with the last element of l which is > x *)
let rec swap l x accu = match l with
| a::b::t when b > x -> a :: (swap (b::t) x accu)
| a::t -> (x::t) @ (a::accu)
| _ -> failwith "this can't happen"
;;

(* permut l m accu computes the permutation p' following p = rev(l)@m,
stores it into accu and recalls itself until p has no successor *)
let rec permut l m accu = match l,m with
| a::_, b::t when a > b -> let p = swap l b t in permut [] p (p::accu)
| _, b::t -> permut (b::l) t accu
| _, [] -> accu
;;
于 2013-03-25T17:24:31.833 回答
0

正如 Kwariz 指出的那样（本质上），您可以对列表使用相同的解决方案。数组解决方案可以在恒定时间内交换数字，但首先扫描它们仍然需要线性时间。使用数字列表，您仍然可以进行线性扫描，以及交换数字的线性操作。

可能会想出一个更漂亮的递归解决方案。问题是您正在使用列表的一个相当“全局”的属性。将其分解为通常的递归部分并不容易。但这并不算太远。一方面，如果您可以对列表的尾部执行操作，那么这也是整个列表的正确结果（重新添加头部）。

于 2013-03-25T18:09:22.240 回答