3

I have been given an array A of integers. Now I have to found out a sub-array(a sub-sequence of original array) where sum of every pair is greater than or equal to a pre-defined K.

What I thought :-

  • Will sort the array in O(nlgn) or O(n) depending upon range of values in array.
  • Find out i in sorted array such that sorted[i] + sorted[i+1]>=k
  • Set max to sorted[i]
  • Traverse the original array to delete all value smaller than max, which is the required sub-sequence

Repeat the above for all the elements of the array.

Running Time :- O(nlgn)

Is the solution optimal ? Can we further improve it ?

Example :-

-10 -100 5 2 4 7 10 23 81 5 25

Sorted Array

-100 -10 2 4 5 5 7 10 23 25 81

Let K = 20

Sub Array : -

10 23 25 81

Had the question been to find out longest sub-array, algorithm suggested by alestanis in the answers would work fine :)

4

4 回答 4

3

这是一种略有不同的方法，由较早的评论之一暗示，类似于 alestanis 的答案，但略有不同，因为它不依赖于拆分数组。它通过数组进行单次传递（尽管这不能保证 O(N) ），并且只需要跟踪两个最小值以及正在考虑的子序列的起点和终点。

要使所有可能对的总和为 20 的连续子序列，两个最小元素的总和必须 >= 20。因此，首先要考虑后续的元素对 (array[0]和array[1]开始)。array[1]如果它们的总和不是 20 或更多，那么继续array[2]. 如果它们加起来达到 20 或更多，则将右侧端点扩大一。如果新元素大于其他两个元素，那么它将与子序列中已有的任何元素相加为 20 或更大，您可以再次展开右手。如果它更少，那么您需要通过几个比较来选择两个最小元素，如果两个新的最小元素现在不等于 20 或更多，则从子序列中删除您刚刚添加的元素，并注意这个特定的子序列，然后从现有子序列的第二个和第三个元素重新开始。最后，您通常会有一个符合约束的子序列列表，并且应该很容易选择第一个或最大的或任何您需要的。

例如，使用您列出的序列：

-10 -100 5 2 4 7 10 23 81 5 25

开始-10, -100。它们的总和不是 20，所以向右移动 1 到-100, 5。同样，这些总和不等于 20，所以继续。总和为 20 的第一对是10, 23. 所以现在，我们将范围扩大到10, 23, 81. 81 大于两个最小值，所以我们再次展开，到10, 23, 81, 5。5 小于 10 和 23，所以新的最小值是 5 和 10，它们的和不等于 20，所以加 5 是错误的，我们需要回溯。我们发现10, 23, 81就是这样一个子序列。接下来我们继续23, 81，这将引导我们到子序列23, 81, 5, 25，它也符合标准。

所以，最后，我们有四个满足条件的可能子序列 - 10, 23, 81、23, 81, 5, 25、81, 5, 25和5, 25。一旦我们有一个包含原始列表中最后一个元素的解决方案，就可以通过不找到其他解决方案来修剪最后两个，这将只留下前两个可能性。从那里我们可以选择第一个或最长的。

于 2012-10-22T19:07:07.937 回答
3

这是一个相当简单的解决方案。

>>> def f(A, k):
...     solution = [item for item in A if 2*item >= k]
...     m = min(solution)
...     for item in A:
...         if item + m >= k and 2*item < k:
...             solution.append(item)
...             break
...     return solution
...
>>> f([-10, -100, 5, 2, 4, 7, 10, 23, 81, 5, 25], 20)
[10, 23, 81, 25]
>>>
于 2012-10-23T01:36:11.113 回答
2

首先，你不能对你的集合进行排序。我认为问题的一部分是找到作为输入给出的原始数组的子数组。

这可以使用一些递归来解决：

  1. 找到数组的两个最小值，m1然后m2
  2. 如果m1 + m2 < K然后将您的数组拆分为最多两个不包含m1和m2同时的较小数组。m1如果and的索引m2是iand jwithi<j那么子数组是[O, j-1]and [i+1, n]。从步骤 1 开始重复。
  3. 如果m1 + m2 >= K那么您当前的数组是您的问题的可行解决方案：返回它的长度。
  4. 添加一些修剪以丢弃无用的数组

让我们将此应用于您的示例：

Initialize max = 0;
A1 = -10* -100* 5 2 4 7 10 23 81 5 25

它的两个最小值是 -10 和 -100。围绕这些值拆分数组，这给了我们一个数组（我们很幸运！）

A2 = 5 2* 4* 7 10 23 81 5 25

两个最小值A2是 2 和 4。我们分成

A3_1 = 5* 4*   and    A3_2 = 2* 7 10 23 81 5* 25

这将继续进行以下迭代：

A3_1 discarded    
A3_2 becomes A4_1 = 2* 7* 10 23 81    A4_2 = 7* 10 23 81 5* 25

A5_1 = 7* 10* 23 81
A5_2 = 7* 10* 23 81        -> Duplicate, discarded
A5_3 = 10* 23 81 5* 25

A6_1 = 10* 23* 81          -> Yay! update max = 3
A6_2 = 10* 23* 81          -> Length <= max. Discarded
A6_3 = 23 81 5* 25         -> Yay! update max = 4

在此示例中，我通过以下方式修剪了搜索空间：

  • 消除重复的子集（这可以通过将它们存储在一个集合中来完成）
  • 丢弃小于或等于当前已知最大长度的子数组

该算法的复杂度为：

  • O(nlogn) 平均，
  • O(n^2) 最坏的情况。当数组被排序并且最小值总是在数组的一侧时会发生这种情况，因此不能将数组拆分为更小的子数组（如示例的第一次迭代）。
于 2012-10-22T17:34:50.453 回答
0 
void sub_array(int ar[],int n,int val)
{
    int max=0;
    for(int i=0;i<n;i++)
    {
        if(ar[max]<ar[i])
            max=i;
    }
    int b[n];
    max=ar[max];
    int p=0;
    int min=0;
    for(int i=0;i<n;i++)
    {
        if(ar[i]+max>val)
        {
            b[p]=ar[i];
            if(ar[i]<max)
            {   
                min=p;
                max=ar[i];
            }
            p++;
        }
        else
        {
            if(ar[i]>max)
            {
                max=ar[i];
                b[min]=ar[i];
            }
        }
    }
    for(int i=0;i<p;i++)
    {
        cout<<b[i]<< "  " ;
    }
}
于 2014-12-11T23:20:03.937 回答