7

给定一个数组（假设为非负整数），我们需要找到最小长度的子集，使得元素之和不小于 K。K 是作为输入提供的另一个整数。

是否有可能有一个时间复杂度为 O(n) [big oh of n] 的解决方案？

我目前的想法是：我们可以在 O(n * log n) 中对数组进行排序，然后从最大数开始迭代排序数组并保持运行总和，直到运行总和变为 >= K。

但是，这将具有 O(n * (log n + 1)) 的最坏情况运行时间。

因此，如果有人可以在 O(n) 时间内分享这样做的想法，我将非常感激..

注意：在这种情况下，子数组的元素不必是原始数组的连续序列

4

6 回答 6

7

有一个线性时间算法可以找到最大的 K 个数字 - http://en.wikipedia.org/wiki/Selection_algorithm。当然，您想要的只是足够大的数字来总计至少 K。

在标准选择算法中，您采用随机枢轴，然后查看有多少数字落在它的每一侧。然后你要么接受要么拒绝一半，然后继续处理另一半。您已经依次查看了每一半中的每个数字 - 每个枢轴阶段的成本是线性的，但是在每个阶段考虑的数据量减少得足够快，以至于总成本仍然只是线性的。

如果您将枢轴以上的所有数字相加，则枢轴阶段的成本仍然是线性的。使用这个，你可以计算出如果接受所有这些数字以及之前选择的任何数字，是否会给你一个加起来至少为 K 的数字集合。如果是这样，你可以放弃其他数字并使用上面的数字下一次传球的枢轴。如果没有，您可以接受枢轴上方的所有数字，并使用枢轴下方的数字进行下一次传递。与选择算法一样，枢轴本身和任何关系都会为您提供一些特殊情况以及尽早找到准确答案的可能性。

（所以我认为您可以使用修改后的选择算法在（随机）线性时间内执行此操作，在该算法中，您可以查看枢轴上方数字的总和，而不是枢轴上方有多少数字。

于 2012-10-23T04:23:44.260 回答
5

这似乎是动态规划的一个问题。构建数组时，您会构建另一个数组，其中包含每个特定索引的累积总和。所以i该数组中的每个都有来自 的总和1..i。

现在很容易看出索引值的总和p..q是SUM(q) - SUM(p-1)（在特殊情况下SUM(0)是0）。显然我在这里使用基于 1 的索引......这个操作是 O(1)，所以现在你只需要一个 O(n) 算法来找到最好的。

一个简单的解决方案是跟踪 ap并q在数组中遍历它们。你开始扩展q。然后你反复收缩p和扩张q，就像毛毛虫在你的阵列中爬行。

展开q：

p <- 1
q <- 1

while SUM(q) - SUM(p-1) < K
    q <- q + 1
end while

现在q是子数组和刚刚超过（或等于）的位置K。子数组的长度为q - p + 1。

在q循环之后，您测试子数组长度是否小于您当前的最佳长度。然后你前进一步p（这样你就不会意外跳过最佳解决方案）并再次前进。

您实际上并不需要创建SUM数组...您可以随时构建子数组总和...您需要返回使用“真实”p而不是之前的那个。

subsum <- VAL(1)
p <- 1
q <- 1

while q <= N
    -- Expand
    while q < N and subsum < K
        q <- q + 1
        subsum <- subsum + VAL(q)
    end while

    -- Check the length against our current best
    len <- q - p + 1
    if len < bestlen
        ...
    end if

    -- Contract
    subsum <- subsum - VAL(p)
    p <- p + 1
end while

笔记：

j_random_hacker 说：这将有助于准确解释为什么只检查该算法检查的 O(n) 个不同子数组而不是所有 O(n^2) 个可能的不同子数组是可以接受的

动态规划的哲学是：

  1. 不要遵循会导致非最佳结果的解决方案路径；和
  2. 使用先前解决方案的知识来计算新的解决方案。

在这种情况下，通过对元素求和来计算单个解决方案候选者（一些(p,q)这样的）。p <= q因为这些元素是正整数，所以我们知道对于任何候选(p,q)解，候选解(p,q+1)都会更大。

所以我们知道如果(p,q)是一个最小的解决方案，那么(p,q+1)就不是。一旦我们有一个候选人，我们就会结束我们的搜索，并测试那个候选人是否比我们迄今为止看到的任何一个更好。这意味着对于每个p，我们只需要测试一个候选人。这导致两者都增加p并且q只会增加，因此搜索是线性的。

另一部分（使用以前的解决方案）来自于认识到这一点sum(p,q+1) = sum(p,q) + X(q+1)和类似sum(p+1,q) = sum(p,q) - X(p)的。因此，我们不必对每一步之间的p所有元素求和。q每当我们推进其中一个搜索指针时，我们只需要加或减一个值。

希望有帮助。

于 2012-10-23T04:15:24.470 回答
3

OP 在他对评论的回答中明确表示，问题是要找到一个子集，而不一定是一个连续的序列（“子数组”这个词确实很糟糕）。那么，我认为mcdowella所指的方法是正确的，包括以下步骤：

从 N 个元素开始，找到 MEDIAN 元素（即想象一个排序数组的第 (N/2) 个元素，您没有也没有构造它）。这是通过“Median of Medians”算法实现的，被证明是 O(n)，请参阅已经给出并在此处重复的 wiki 参考：Selection algorithm，请参阅有关 Median of Median 算法的部分

具有中值元素：线性扫描整个集合，并在“下方”和“上方”中进行分区，同时对每个“一半”进行求和、计数和做任何你想要跟踪的事情。这一步（也是）O（N）。

完成扫描后，如果“上半部分”-总和高于目标 (K)，您将忘记下半部分并重复上半部分的过程，其大小为（大约）N/2。另一方面，如果“上半部分”总和小于 K，则将上半部分添加到最终结果中，从 K 中减去其总和，然后对下半部分重复该过程。

总而言之，您处理大小为 N、N/2、N/4、N/8 等的集合，每个集合相对于它们各自的大小 M 在 O(M) 中，因此总体内容在 N 中也是线性的，因为 N + N/2 + N/4 + N/8 ... 保持在 2N 以下。

于 2012-10-23T09:15:19.463 回答
1

这是一个应该足够快的解决方案。我猜它几乎是线性的。

def solve(A, k):
    assert sum(A) >= k
    max_ = max(A)
    min_ = min(A)
    n = len(A)
    if sum(A) - min_ < k:
        return A
    bucket_size = (max_ - min_)/n + 1
    buckets = []
    for i in range(n):
        buckets.append([])
    for item in A:
        bucket = (item - min_)/bucket_size
        buckets[bucket].append(item)

    solution = []

    while True:
        bucket = buckets.pop() #the last bucket
        sum_ = sum(bucket)
        if sum_ >= k:
            #don't need everything from this bucket
            return solution + solve(bucket, k)
        else:
            k -= sum_
            solution += bucket

print solve([5,2,7,52,30,12,18], 100)
"[52, 30, 18]"
于 2012-10-23T05:16:22.660 回答
0

我相信“子数组”一词意味着数组的连续部分（就像这里，另一个问题作为例子）。

所以有一个简单的 O(n) 算法来找到最小长度子数组：

为第一个元素设置两个索引（左、右）并将它们移动到数组的末尾。检查这些索引之间的和，向右推进指针，如果和太小（或指针相等），如果和大则向左推进

于 2012-10-23T05:17:32.197 回答
0

根据数组的定义，子数组必须是连续的。

使用 2 个指针（开始，结束）。将它们初始化到数组的开头。跟踪 (start, end) 之间的当前总和，并将 end 一个一个向右移动。每次移动结束指针时，sum = sum + array[end]。

当 sum >= target 时，开始向右移动 start 并继续跟踪 sum 为 sum = sum - array[start]。

在向右移动开始的同时，继续检查总和仍然不低于目标。我们还需要通过 length = end - start + 1 以及 minLength = min(minLength, length) 来跟踪长度。

现在，当我们将两个指针尽可能向右移动时，我们只需要返回 minLength。

总体思路是先找到一个满足条件（sum >= target）的“窗口”，然后每次移动窗口时将窗口向右滑动一个元素，并保持窗口大小最小。

于 2013-10-16T04:09:18.620 回答