1

我遇到了另一个我试图在 Scala 中解决的codechef 问题。问题陈述如下：

Stepford Street是一条死胡同。Stepford Street 上的房子被富有的百万富翁买下。他们对它们进行了广泛的改造，以便随着沿街的推进，建筑物的高度迅速增加。然而，并非所有的百万富翁都是生来平等的。一些人拒绝跟随这一趋势，并将他们的房屋保持在原来的高度。因此，由此产生的高度进展受到干扰。比佛利山庄市政公司宣布了一场寻找最有序街道的竞赛。最有序街道的标准设置如下：如果街道中存在比所考虑的房子高度低的房子，那么这对（当前房子，后来的房子）计入 1 分的无序度指数街道。后面的房子不必与现在的房子相邻。注意：一条街道上没有两栋房子的高度相同 例如，对于输入：1 2 4 5 3 6 对 (4,3), (5,3) 形成无序对。因此该数组的无序度指数为 2。由于确定无序度的标准很复杂，BHMC 已请求您帮助自动化该过程。你需要编写一个高效的程序来计算街道的无序度指数。

提供的示例输入输出如下：

输入：1 2 4 5 3 6

输出：2

输出为 2 因为有两对 (4,3) 和 (5,3)

为了解决这个问题，我认为我应该使用 MergeSort 的变体，当左元素大于右元素时递增 1。

我的scala代码如下：

    def dysfunctionCalc(input:List[Int]):Int = {
        val leftHalf = input.size/2
        println("HalfSize:"+leftHalf)

        val isOdd = input.size%2
        println("Is odd:"+isOdd)

        val leftList = input.take(leftHalf+isOdd)
        println("LeftList:"+leftList)

        val rightList = input.drop(leftHalf+isOdd)
        println("RightList:"+rightList)

        if ((leftList.size <= 1) && (rightList.size <= 1)){
                println("Entering input where both lists are <= 1")
                             if(leftList.size == 0 || rightList.size == 0){
                                      println("One of the lists is less than 0")
                                        0
                                }
                             else if(leftList.head > rightList.head)1 else 0
     }       
     else{
             println("Both lists are greater than 1")
             dysfunctionCalc(leftList) + dysfunctionCalc(rightList)
     }
   }

首先，我的逻辑是错误的，它没有合并阶段，我不确定将基本情况的结果渗透到堆栈中并将其与其他值进行比较的最佳方法是什么。此外，使用递归来解决这个问题可能不是最好的方法，因为对于大型列表，我可能会炸毁堆栈。此外，我的代码也可能存在风格问题。

如果有人能指出其他缺陷和解决这个问题的正确方法，我会很棒。

谢谢

4

5 回答 5

2

这是我的尝试，我不使用 MergeSort 但它似乎解决了问题：

def calcDisorderness(myList:List[Int]):Int = myList match{
  case Nil => 0
  case t::q => q.count(_<t) + calcDisorderness(q)
}

scala> val 输入 = List(1,2,4,5,3,6)

输入：List[Int] = List(1, 2, 4, 5, 3, 6)

scala> calcDisorderness（输入）

res1: 整数 = 2

问题是，有没有办法降低复杂性？

编辑：相同函数的尾递归版本和函数参数中默认值的酷用法。

def calcDisorderness(myList:List[Int], disorder:Int=0):Int = myList match{
  case Nil => disorder
  case t::q => calcDisorderness(q, disorder + q.count(_<t))
}
于 2012-04-25T19:13:53.247 回答
2

假设您将列表分成三部分：您正在考虑的项目、左侧的项目和右侧的项目。进一步假设左边的那些在一个排序集中。现在你只需要遍历列表，将项目从“右”移动到“考虑”，从“考虑”到“左”；在每一点上，您都会查看大于您的项目的排序集子集的大小。一般来说，大小查找可以O(log(N))在 add-element 中完成（例如，使用 Red-Black 或 AVL 树）。所以你有O(N log N)表现。

现在的问题是如何在 Scala 中有效地实现这一点。事实证明，Scala 有一个用于其排序集的红黑树TreeSet，并且实现实际上非常简单（这里是尾递归形式）：

import collection.immutable.TreeSet
final def calcDisorder(xs: List[Int], left: TreeSet[Int] = TreeSet.empty, n: Int = 0): Int = xs match {
  case Nil => n
  case x :: rest => calcDisorder(rest, left + x, n + left.from(x).size)
}

不幸的是，这left.from(x).size需要O(N)时间（我相信），这会产生二次执行时间。那不好-您需要的是IndexedTreeSet可以在其中执行indexOf(x)的操作O(log(n))（然后使用 迭代n + left.size - left.indexOf(x) - 1）。您可以构建自己的实现或在网络上找到一个。例如，我在此处（此处为 API）找到了一个完全正确的 Java。

顺便说一句，进行归并排序的问题在于您不能轻松地累积工作。通过合并一对，您可以跟踪它的无序程度。但是，当您合并第三个列表时，您必须看到它相对于其他两个列表的乱序程度，这会破坏您的分而治之的策略。（我不确定是否可以找到一些不变量，如果您跟踪它，可以让您直接计算。）

于 2012-04-26T00:51:23.773 回答
1

基于合并排序的解决方案。不是超级快，潜在的减速可能在“xs.length”中。

def countSwaps(a: Array[Int]): Long = {
    var disorder: Long = 0

    def msort(xs: List[Int]): List[Int] = { 
        import Stream._
        def merge(left: List[Int], right: List[Int], inc: Int): Stream[Int] = {
            (left, right) match {
                case (x :: xs, y :: ys) if x > y =>
                    cons(y, merge(left, ys, inc + 1))
                case (x :: xs, _) => {
                    disorder += inc
                    cons(x, merge(xs, right, inc))
                }
                case _ => right.toStream
            }
        }

        val n = xs.length / 2 
        if (n == 0)
            xs 
        else { 
            val (ys, zs) = xs splitAt n 
            merge(msort(ys), msort(zs), 0).toList
        } 
    }

    msort(a.toList)
    disorder
}
于 2012-06-22T19:29:51.667 回答
1

另一种基于合并排序的解决方案。非常快：没有 FP 或 for 循环。

def countSwaps(a: Array[Int]): Count = {
    var swaps: Count = 0

    def mergeRun(begin: Int, run_len: Int, src: Array[Int], dst: Array[Int]) = {
        var li = begin
        val lend = math.min(begin + run_len, src.length)
        var ri = begin + run_len
        val rend = math.min(begin + run_len * 2, src.length)

        var ti = begin
        while (ti < rend) {
            if (ri >= rend) {
                dst(ti) = src(li); li += 1
                swaps += ri - begin - run_len
            } else if (li >= lend) {
                dst(ti) = src(ri); ri += 1
            } else if (a(li) <= a(ri)) {
                dst(ti) = src(li); li += 1
                swaps += ri - begin - run_len
            } else {
                dst(ti) = src(ri); ri += 1
            }
            ti += 1
        }
    }

    val b = new Array[Int](a.length)
    var run = 0
    var run_len = 1
    while (run_len < a.length) {
        var begin = 0
        while (begin < a.length) {
            val (src, dst) = if (run % 2 == 0) (a, b) else (b, a)
            mergeRun(begin, run_len, src, dst)
            begin += run_len * 2
        }
        run += 1
        run_len *= 2
    }

    swaps
}

将上面的代码转换为函数式：没有可变变量，没有循环。所有递归都是尾调用，因此性能良好。

def countSwaps(a: Array[Int]): Count = {
    def mergeRun(li: Int, lend: Int, rb: Int, ri: Int, rend: Int, di: Int, src: Array[Int], dst: Array[Int], swaps: Count): Count = {
        if (ri >= rend && li >= lend) {
            swaps
        } else if (ri >= rend) {
            dst(di) = src(li)
            mergeRun(li + 1, lend, rb, ri, rend, di + 1, src, dst, ri - rb + swaps)
        } else if (li >= lend) {
            dst(di) = src(ri)
            mergeRun(li, lend, rb, ri + 1, rend, di + 1, src, dst, swaps)
        } else if (src(li) <= src(ri)) {
            dst(di) = src(li)
            mergeRun(li + 1, lend, rb, ri, rend, di + 1, src, dst, ri - rb + swaps)
        } else {
            dst(di) = src(ri)
            mergeRun(li, lend, rb, ri + 1, rend, di + 1, src, dst, swaps)
        }
    }

    val b = new Array[Int](a.length)

    def merge(run: Int, run_len: Int, lb: Int, swaps: Count): Count = {
        if (run_len >= a.length) {
            swaps
        } else if (lb >= a.length) {
            merge(run + 1, run_len * 2, 0, swaps)
        } else {
            val lend = math.min(lb + run_len, a.length)
            val rb = lb + run_len
            val rend = math.min(rb + run_len, a.length)
            val (src, dst) = if (run % 2 == 0) (a, b) else (b, a)
            val inc_swaps = mergeRun(lb, lend, rb, rb, rend, lb, src, dst, 0)
            merge(run, run_len, lb + run_len * 2, inc_swaps + swaps)
        }
    }

    merge(0, 1, 0, 0)
}
于 2012-06-24T22:48:41.090 回答
0

在我看来，关键是将列表分解为一系列升序。例如，您的示例将分解为 (1 2 4 5)(3 6)。第一个列表中的任何项目都不能结束一对。现在你对这两个列表进行一种合并，向后工作：

  • 6 > 5，所以 6 不能成对
  • 3 < 5，所以它是一对
  • 3 < 4，所以它是一对
  • 3 > 2，所以我们完成了

从定义中我不清楚如何处理超过 2 个这样的序列。

于 2012-04-25T18:23:27.827 回答