即使学完课程,还是继续回来请教老师DP问题

来源:11-1 结语

哈哈哈蜜瓜

2018-03-10

今晚朋友做笔试碰到一条DP题:一个长度为2n的数组,任意两个元素组合,求每个组合数组的最小值加起来的最大值,比如数组[1,4,3,2],如可以组成[1,4][3,2],[4,3][1,2],[1,3][4,2],那每组最小元素最大之和就是1+3=4,代码如下:

function findMaxGroup(arr) {
    if (!arr) return 0
    if (arr.length <= 2) return Math.min(arr[0], arr[1])
    let temp = [],
        res = [],
        max = 0,
        k = 1;
    res[0] = Math.min(arr[0], arr[1])
    for (let i = 3; i < arr.length; i += 2) {
        for (let j = 0; j < i; j++) {
            for (let n = j + 1; n <= i; n++) {
                temp.push([arr[j], arr[n]])
            }
        }
        for (let i = 0; i < temp.length; i++) {
            max = Math.max(max, Math.min.apply(null, temp[i]))
        }
        res[k] = max + res[k - 1]
        temp = []
        max = 0
        k++
    }
    return res[res.length - 1]
}

做完自己都崩溃了,时间复杂度大到没朋友,求老师指点下可以优化什么地方

写回答

1回答

liuyubobobo

2018-03-11

为什么觉得就是贪心。要让最小值最大,大的数字就要尽量和大的数字配对,这样才能让大的数字在数字对中成为最小值。所以排序以后两两结合就好了。我时间有限没有严格证明,但直觉上应该没有错。复杂度O(nlogn)。

0
1
哈哈哈蜜瓜
多谢老师,脑残了,这么简单居然没想到是贪心
2018-03-12
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程