3

整数の配列Aが与えられました。ここで、すべてのペアの合計が事前定義されたK以上であるサブ配列（元の配列のサブシーケンス）を見つける必要があります。

私が思ったこと：-

  • 配列内の値の範囲に応じて、配列をO（nlgn）またはO（n）でソートします。
  • 次のようなソートされた配列でiを見つけますsorted[i] + sorted[i+1]>=k
  • maxをに設定sorted[i]
  • 元の配列をトラバースして、必要なサブシーケンスであるmaxよりも小さいすべての値を削除します

配列のすべての要素について上記を繰り返します。

実行時間 ：-O(nlgn)

ソリューションは最適ですか？さらに改善できますか？

例 ：-

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

ソートされた配列

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

させてK = 20

サブ配列：-

10 23 25 81

質問が最長のサブ配列を見つけることだったとしたら、答えの中でalestanisによって提案されたアルゴリズムはうまくいくでしょう:)

4

4 に答える 4

3

これはわずかに異なるアプローチであり、以前のコメントの1つによって示唆され、alestanisによる回答に似ていますが、配列の分割に依存しないという点でわずかに異なります。配列を1回通過し（ただし、O（N）を保証するものではありません）、考慮されているサブシーケンスの開始点と終了点だけでなく、2つの最小値を追跡する必要があります。

連続するサブシーケンスですべての可能なペアの合計が20になるには、2つの最小要素の合計が> = 20である必要があります。したがって、後続の要素のペア（array[0]およびarray[1]開始）を検討することから始めます。合計が20以上にならない場合は、にarray[1]進み、array[2]。合計が20以上の場合は、右側のエンドポイントを1つ拡張します。新しい要素が他の2つよりも大きい場合は、サブシーケンスにすでに含まれているものを含めて合計が20以上になり、右手をもう一度展開できます。それより少ない場合は、いくつかの比較で2つの最小要素を選択する必要があります。また、2つの新しい最小要素の合計が20以上にならない場合は、追加した要素をサブシーケンスから削除し、注意してください。この特定のサブシーケンスは、既存のサブシーケンスの2番目と3番目の要素からやり直します。最後に、一般に、制約に適合するサブシーケンスのリストがあり、最初または最大、あるいは必要なものを簡単に選択できるはずです。

たとえば、リストしたシーケンスを使用します。

-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は2つの最小値の両方よりも大きいので、再び展開して10, 23, 81, 5。5は10と23の両方よりも小さいため、新しい最小値は5と10であり、合計は20になりません。したがって、5を追加するのは間違いであり、後戻りする必要があります。10, 23, 81そのようなサブシーケンスの1つが見つかります。次に、に進みます。これにより、基準も満たす23, 81サブシーケンスに移動します。23, 81, 5, 25

したがって、最後に、基準を満たす4つの可能なサブシーケンスがあります- 10, 23, 81、、、、および。元のリストの最後の要素を含むソリューションができたら、追加のソリューションを見つけないことで、最後の2つを取り除くことができます。これにより、最初の2つの可能性だけが残ります。そこから、最初または最長のいずれかを選択できます。23, 81, 5, 2581, 5, 255, 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. 配列の2つの最小値を見つけm1、m2
  2. 次に、配列を含まない最大2つの小さな配列にm1 + m2 < K分割します。とのインデックスがとである場合、サブ配列はとです。手順1から繰り返します。m1m2m1m2iji<j[O, j-1][i+1, n]
  3. その場合m1 + m2 >= K、現在の配列が問題の実行可能な解決策です。その長さを返します。
  4. 不要な配列を破棄するためにいくつかのプルーニングを追加します

これをあなたの例に適用してみましょう：

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

その2つの最小値は-10と-100です。これらの値を中心に配列を分割すると、配列は1つだけになります（幸運です！）

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

の2つの最小値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 に答える