求问一道面经算法题，不知道用哪种方法

今天刚面了一家小公司，给的题目初看不是很难但是一下子不知道用哪种方法，求各位大神解惑
input是一个sorted integer array和integer limit , 要求返回output 是最优二维数组，其中子数组之和小于等于limit, 满足条件下要求二位数组的size 最小, 顺序无所谓

Example 1:
input: [1, 2, 2, 3, 4, 5, 6] , 6
output: [[1, 5], [2, 4], [2, 3], [6]]

Example 2:
input: [2, 2, 2, 3, 3, 5] , 6
output: [[2, 2, 2], [3, 3], [5]]

感觉用two pointers 和dfs 都不太能做出来，求各位大神给点思路

楼主问了数据规模没有？
这道题看起来像是2的n次方
我只能想到很笨的解法。而且和sort不sort没关系。
用dp存数组的任意状态，用二进制表示数组那些element 被拿走了，那些还在，比如11111111就是初始状态，
状态转移就是取任意个还没被取走的数，他们和小于limit作为一个result里面的element
[1, 2, 3] , 3
start : 111
f(111) = min(1 + f(110), 1 + f(101), 1 + f(001), 1 + f(011))
对应的就是
1. 取出3
2. 跳过 3 取出2
3. 跳过 3 取出2 取出1
4, 跳过 3 跳过 2 取出1

dp的size是2的n次方，状态转移也是2的n次方（数组中未被取走的数所有combination）

今天正好刷到原题。1986
果真是数据规模很小只有14，是二的n次方

a87009751 发表于 2022-4-2 12:52
我补充了，要用min pq。

用PriorityQueue找剩余空间最大的船看上去像那么回事，但你一个数多拆几次一样也不行了啊，能过[1,2,2,2,2,2,3,3,3], 10的case， 到[2,3,3,4,4,4,5,6,7,10]，12又不行了。NP完全的题要求精确解而不是估算的话，就是没法套881那种题去贪心的啊。

我有个问题，按你的描述，为什么[1]这种没有在example1来的output里呢

小亩_psg90s6 发表于 2022-3-30 15:36
我有个问题，按你的描述，为什么[1]这种没有在example1来的output里呢

有啊， 你看1和5 配对了， example 1 output 是[[1, 5], [2, 4], [2, 3], [6]]

SDFS 发表于 2022-03-30 15:38:54
有啊， 你看1和5 配对了， example 1 output 是, , , ]

可以assume数组里的数都应该被用到吗？

小亩_psg90s6 发表于 2022-3-30 15:41
可以assume数组里的数都应该被用到吗？

可以，可以assume:
1. 数组所有的数都会被用到有且仅有一次
2. 数组中任何一个数都不会超过limit

小亩_psg90s6 发表于 2022-03-30 15:36:59
我有个问题，按你的描述，为什么这种没有在example1来的output里呢

因为题目要求二维数组size最小吧？

SDFS 发表于 2022-03-30 15:43:37
可以，可以assume:
1. 数组所有的数都会被用到有且仅有一次
2. 数组中任何一个数都不会超过limit

你用哈希表存frequency，然后剔除掉在数组里数字=limit的数。然后
Res=[]
for i in range(limit):
        for j in range(len(nums)):
                if k-nums[i] in dic:
                        res.append([nums[i],k-nums[i]])
                        if dic[k-nums[i]]>1:
                                dic[k-nums[i]]-=1
                        else:
                                del dic[k-nums[i]]

补充内容 (2022-03-31 07:02 +08:00):
第一个循环写错了，是backward，从limit 循环到0

补充内容 (2022-03-31 07:03 +08:00):
大概思路就是用字典存次数，然后从最limit开始往下循环找，一直找到0，字典为空就可以结束，复杂度是limit*n，

是个取均值问题，假设和是sum，上限是n，上限越小越难分，只考虑小的上限。最好情况就是分成sum/n组。
个人感觉要排序然后先把大的数字搞定？大数在不超过上限的情况下尽量和其他大数字搭配，然后剩下小数字扎堆这个方案是最优的？
想不出来严格的数学证明。

随便写了一下，没经测试，不知道对不对
vector<vector<int>> compute (vector<int> a, int k) {
    vector<vector<int>> v;
    v.push_back({})
    for (int i = 0, j = n - 1, sum = 0; i <= j; v.push_back({}), sum = 0) {
        if (i == j) {
            v.back().push_back(a[i]);
            return;
        }
        while ((sum += a[j]) < k) {
            v.back().push_back(a[j--]);
        }
        while ((sum += a[i] < k)) {
            v.back().push_back(a[i++]);
        }
    }
    return v;
}

双指针 + greedy就完事了呀，假设数组是升序排序，你从右往左检查，只要num > limit，就添加到2D Array里面，如果num <= limit，就从左往右看看有多少数字能加起来不超过limit，只要超过就把之前扫描的数字追加到2D array里面。这样做的原因就是数组有序，最大值只要大于limit就只能单独成一组，小于limit就尽可能结合更多的数字，那就从最左边开始扫描。注意数字为0和负数情况，这种会越加越小，或者不变，所以num == limit还要从左往右囊括更多的数字。

空间复杂度是O（n），不需要其他数据结构；时间复杂度个人认为是O（n），从右扫描就是每个数字扫描一次，从左扫描虽然会最多扫描到n个，但是只要扫描到n，从右就不需要扫描了，不会出现每个数字扫描多达n次的情况，但要严格证明就比较难说明了，不想想啦