如何在Scala中使用合并排序来计算Int列表的倒置计数？
如何在Scala中使用合并排序来计算Int列表的倒置计数？
提问于 2018-06-05 18:07:46
def mergeSort(xs: List[Int]): List[Int] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[Int], ys: List[Int]): List[Int] =
(xs, ys) match {
case(Nil, ys) => ys
case(xs, Nil) => xs
case(x :: xs1, y :: ys1) =>
if (x < y) {
x :: merge(xs1, ys)
}
else {
y :: merge(xs, ys1)
}
}
val (left, right) = xs splitAt(n)
merge(mergeSort(left), mergeSort(right))
}
}数组的倒置计数表示该数组离排序的距离有多远。如果数组已经排序，则反转计数为0。如果数组按逆序排序，则倒置计数为最大值。从形式上讲，如果ai > aj和i
例如:序列2，4，1，3，5有三个倒数(2，1)，(4，1)，(4，3)。
因此，如果将此列表(2，4，1，3，5)传递给函数，则反转计数应为3。
我如何添加一个变量来获得数字？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-06 05:43:26
也许像will这样的东西会有帮助
def mergeSort(xs: List[Int], cnt: Int): (List[Int], Int) = {
val n = xs.length / 2
if (n == 0) (xs, cnt)
else {
def merge(xs: List[Int], ys: List[Int], cnt: Int): (List[Int], Int) =
(xs, ys) match {
case(Nil, ys) => (ys, cnt)
case(xs, Nil) => (xs, cnt)
case(x :: xs1, y :: ys1) =>
if (x <= y) {
val t = merge(xs1, ys, cnt)
(x :: t._1, t._2)
}
else {
val t = merge(xs, ys1, cnt + xs.size)
(y :: t._1, t._2)
}
}
val (left, right) = xs splitAt(n)
val leftMergeSort = mergeSort(left, cnt)
val rightMergeSort = mergeSort(right, cnt)
merge(leftMergeSort._1, rightMergeSort._1, leftMergeSort._2 + rightMergeSort._2)
}
}我在所有函数调用中都传递了一个元组，仅此而已。
当我们发现一个列表的第一个元素小于第二个列表的第一个元素时，我递增cnt的值。在这个场景中，我们将list.length添加到cnt中。查看代码，以获得更清晰的视图。
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50697468
复制相关文章
相似问题