1

我有一个矩阵 [M x N]，在矩阵的每个单元格中，都有一个数组 [N]（从最大值到最小值排序）。

我必须编写一个函数，将其重构Matrix为 one data-structure，从 min 到 max 排序？

具有最佳的记忆力和时间。

我的解决方案不是最优的，而且成本非常高（内存和时间）。
Solution: 遍历矩阵并将每个数组拉到一个数组：O(N^2 - memory&time) 之后对该数组进行排序 O(N - memory&time)。

什么算法最适合我？

4

3 回答 3

1

这个答案可能有点离题，因为它使用的是 f# 而不是 c#，但是该算法可以重复使用，但我认为用 f# 编写它会更快。这是一个示例解决方案，我合并了我对问题的评论中描述的所有结果：

let rec orderedMerge xs ys =
    match xs,ys with
    | [],l | l,[] -> l
    | x::xs', y::ys' ->
        if x < y then x :: (orderedMerge xs' ys)
        else y :: (orderedMerge xs ys')

let rec orderNestedMerge xxs =
    match xxs with
    | x::[] -> x
    | x::y::[] -> orderedMerge x y
    | x::y::xxs' -> orderedMerge (orderedMerge x y) (orderNestedMerge xxs')

let rec orderNested2Merge xxxs = 
    match xxxs with
    | x::[] -> orderNestedMerge x
    | x::y::[] -> orderedMerge (orderNestedMerge x) (orderNestedMerge y)
    | x::y::xxxs' -> orderedMerge (orderedMerge (orderNestedMerge x) (orderNestedMerge y)) (orderNested2Merge xxxs')

let l1 = [1;5;6;10]
let l2 = [2;3;9;11]
let l3 = [3;4;5;8]
let l4 = [2;8;9;12]
let m1 = [l1;l2]
let m2 = [[l1;l2];[l3;l4]]
let r1 = orderedMerge l1 l2
let r2 = orderNestedMerge m1
let r3 = orderNested2Merge m2

结果：

val m1 : int list list = [[1; 5; 6; 10]; [2; 3; 9; 11]]
val m2 : int list list list = [[[1; 5; 6; 10]; [2; 3; 9; 11]]; [[3; 4; 5; 8]; [2; 8; 9; 12]]]
val r1 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r2 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r3 : int list = [1; 2; 2; 3; 3; 4; 5; 5; 6; 8; 8; 9; 9; 10; 11; 12]

我还没有计算过它的表现，但我认为它很好。附带说明一下，我认为您无法实现同时具有最佳内存和时间利用率的解决方案，您必须首先关注其中一个，然后使另一个尽可能好。

更新： 您可以对此解决方案进行的一项改进是使用尾递归，重写它以使用尾递归应该不难。

于 2013-10-02T12:09:57.983 回答
0

您基本上是在尝试实现合并排序，但部分子案例已经排序。如果您只是以合并排序的方式递归合并列表对，并假设您实际上意味着列表的长度与矩阵边的长度大致相同，那么您的运行时间为 O(n^3 log( n^2)) 而不是你原来的建议是 O(n^3 log(n^3))，或者它快 33% 左右（我在这里严重滥用 bigO 表示法）。

于 2013-10-02T12:59:11.207 回答
0

你说的算法不可能有时间和空间复杂度O(N^2)。我在下面指定了我的分析：

算法 1 - 复杂度：O(M N^2 log (M N^2))

这是您描述的算法。

1）遍历矩阵并将每个数组拉到一个数组：O(M*N^2)复制所有元素需要时间

2) 之后对该数组进行排序。您可能排序的最快的是O(M*N^2 log (M*N^2)).

因此，整体时间复杂度将是O(M*N^2 log (M*N^2))。

算法 2 - 复杂度：O(M N^2 × log M N)

改编自Algorithm for n-way merge

  1. 创建优先队列
  2. 遍历 MxN 数组中的每个数组
    1. 使用第一个值作为优先键将对 (nextNumberIn({i,j}th array), {i,j}) 入队
  3. 虽然队列不为空
    1. 队列头 ( number, {i,j}) 出队
    2. 输出number
    3. 如果第 {i,j} 个数组未耗尽
      1. enqueue (nextNumberIn({i,j}th array), {i,j})

由于将元素添加到优先级队列可以在对数时间内完成，因此第 2 项是O(M*N × log M*N)。由于 while 循环的（几乎所有）迭代添加了一个元素，因此整个 while 循环将为O(M*N^2 × log M*N)，其中 M*N^2 是要排序的元素总数。

由于步骤 3 的复杂度占主导地位，因此总时间复杂度将为O(M*N^2 × log M*N).

空间复杂度

对于上述两种算法，O(M*N^2)存储新数组的空间复杂度都最低。除此之外，算法#1 将需要O(log (M*N^2))额外的空间用于排序步骤，而算法#2 将需要额外的空间O(M*N)用于优先级队列。

于 2013-10-02T13:27:25.440 回答