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。
我如何添加一个变量来获得数字?
发布于 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中。查看代码,以获得更清晰的视图。
希望这能有所帮助!
https://stackoverflow.com/questions/50697468
复制相似问题