时间戳

首页 > 解决方案 > 如何使用数组模块函数更改 for 循环？

arrays - 如何使用数组模块函数更改 for 循环？

问题描述

这是学校的作业。我正在尝试创建一个函数，它接受一个数组 A 并创建一个新数组 B，它告诉数组中有多少个重复数字。例如 A 是这样的：

A = [|2;9;9;2;2;4|]

B 将是：

B = [|3;2;2;3;3;1|]

纽约的代码现在是这样的，并且运行良好：

let A = [|2;9;9;2;2;4|]
let n = A.Length - 1

let B = Array.create A.Length 0
for i = 0 to n do 
    Array.iter (fun j -> if i <> j && A.[i]=j then B.[i] <- (B.[i] + 1)) A

printfn "%A" B

我的问题是，渐近时间是多少？我知道第一个 for 循环是 O(n)，但是 Array.iter 呢？有没有办法用数组函数切换第一个 for 循环？

标签： arraysf#

解决方案

Array.iter在数组长度上是线性的，所以你的 for 循环在时间复杂度上本质上是 O(n²)。可以用另一个循环替换循环，Array.iter但不会改变时间复杂度。

如果你能以任何你想要的方式解决问题，我建议使用 Map 来聚合数字及其频率，然后将原始数组映射到显示这些频率的数组。由于这是一项学校作业，您可能应该等到提交截止日期之后再查看以下代码：

let numFrequency (a : _ []) =
    let m =
        (Map.empty, a)
        ||> Array.fold (fun m n ->
            Map.tryFind n m
            |> Option.defaultValue 0
            |> fun x -> Map.add n (x + 1) m)
    Array.map (fun n -> Map.find n m) a

let A = [|2; 9; 9; 2; 2; 4|]

let B = numFrequency A

printf "%A\n%A\n" A B

推荐阅读