仅使用两个操作将数组转换为已排序的数组

Question

我在一个在线论坛上发现了这个问题:真的对如何解决这个问题感兴趣:

给定正整数的数组A. 以最低成本将其转换为排序数组.唯一有效的操作是:
1)减少成本= 1
2)使用cost = value of element从数组中完全删除元素

这是一家面向技术公司的面试问题

Answer 1

注意:原来的答案已被替换为我更有信心的答案(我也可以解释).这两个答案在我的测试用例集上产生了相同的结果.

您可以使用动态编程方法解决此问题.关键的观察是将数字减少到原始数组中找不到的值是没有意义的.(非正式证明:假设你减少许多O1的值X,是不是在原来的顺序,以避免删除了一些O2 > X.从结果序列然后你就可以减小O1到O2代替,并通过降低成本O2-X).

现在解决方案变得易于理解:它是一个二维DP.如果我们将原始序列的不同元素的元素d排序为排序数组s,则长度d成为DP的第一维; 长度s成为第二个维度.

我们宣布dp[d.Length,s.Length].值dp[i,j]是解决子问题的成本,d[0 to i]同时保持解决方案的最后一个元素s[j].注意:此成本包括消除成本,d[i]如果小于s[j].

第一行dp[0,j]被计算为修整的成本d[0]来s[j],或零,如果d[0] < s[j].的值dp[i,j]下一行被计算为最小的dp[i-1, 0 to j] + trim,在那里trim是修整的成本d[i]到s[j],或者d[i]如果它需要被消除,因为s[j]比更大d[i].

答案计算为最后一行的最小值dp[d.Length-1, 0 to s.Length].

这是C#中的一个实现:

static int Cost(int[] d) {
    var s = d.Distinct().OrderBy(v => v).ToArray();
    var dp = new int[d.Length,s.Length];
    for (var j = 0 ; j != s.Length ; j++) {
        dp[0, j] = Math.Max(d[0] - s[j], 0);
    }
    for (var i = 1; i != d.Length; i++) {
        for (var j = 0 ; j != s.Length ; j++) {
            dp[i, j] = int.MaxValue;
            var trim = d[i] - s[j];
            if (trim < 0) {
                trim = d[i];
            }
            dp[i, j] = int.MaxValue;
            for (var k = j ; k >= 0 ; k--) {
                dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
            }
        }
    }
    var best = int.MaxValue;
    for (var j = 0 ; j != s.Length ; j++) {
        best = Math.Min(best, dp[d.Length - 1, j]);
    }
    return best;
}

这种直接实现具有空间复杂性O(N^2).您可以O(N)通过观察同时仅使用最后两行来减少它.