40

n配列内の正の実数が与えられたとき、この集合の中に、その和が の範囲にあるような 3 つの要素が存在する(1, 2)かどうかを調べます。線形時間と一定空間でそれを行います。

  • 配列は順序付けされていません。
  • 数値は正です
  • 数字は実数です

どんな助けでも大歓迎です。ありがとう。

4

8 に答える 8

51

秘訣は、考えられる解を分類する方法を見つけ出し、それぞれに対して線形時定数空間の解を考え出すことです。

3 つの範囲を検討してくださいX = (0,2/3), Y = [2/3,1], Z = (1,2)。最大で 1 つの値を取得できますZ(2 つの値が から取得された場合Z、合計は を超えます1+1=2)。同様に、少なくとも 1 つの値は から取得する必要がありますX。a <= b <= cとなるように 3 つの値があったとし1 <= a+b+c <= 2ます。次に、実行可能な解のクラスを検討します。

A) `a \in X, b \in X, C \in X` 
B) `a \in X, b \in X, C \in Y` 
C) `a \in X, b \in X, C \in Z` 
D) `a \in X, b \in Y, C \in Y` 
E) `a \in X, b \in Y, C \in Z`

では、各ケースをどのようにテストできますか?

ケース A のテストは信じられないほど簡単です。合計は 2 未満であることが保証されているため、最大の合計 (X の最大の 3 つの要素) が 1 を超えることをテストするだけで済みます。

ケース C のテストは非常に簡単です。合計が 1 を超えることが保証されているため、合計が 2 を下回っているかどうかを確認するだけで済みます。そのためには、X の最小の 2 つの値とZ の最小値

ケース D と E は C に似ています (合計は少なくとも 4/3 > 1 でなければならないため、各クラスで可能な限り小さい値を選択します)。

ケース B は唯一のトリッキーなケースです。 0 < a+b < 4/3と2/3 <= c <= 1。ケース B を処理するために、次の間隔を考慮します: X1 = (0, 1/2)、X2 = [1/2 2/3)、Y = [2/3, 1]。

これにより、次の 3 つの有効なケースが発生します。

B1. X1 に a、X2 に b、Y に c

B2. X1 で a、X1 で b、Y で c

B3. X2 で a、X2 で b、Y で c

ケース B1 & B3 : 3 つの数値の合計は常に 1 より大きいため、最小値を取り、それが 2 より小さいかどうかを確認します。

ケース B2 : 3 つの数値の合計は常に 2 未満であるため、最大の合計を取り、1 より大きいかどうかを確認します。

要約すると、テストは次のとおりです。

  • |X| >= 3とXmax(1) + Xmax(2) + Xmax(3) >= 1
  • |X| >= 2、|Z| >= 1、およびXmin(1)+Xmin(2)+Zmin(1) <= 2
  • |X| >= 1、|Y| >= 2、およびXmin(1)+Ymin(1)+Ymin(2) <= 2
  • |X| >= 1、|Y| >= 1、|Z| >= 1、およびXmin(1)+Ymin(1)+Zmin(1) <= 2
  • |X| >= 2、|Y| >= 1、およびXmax(1) + Xmax(2) + Ymin(1) < 2
  • |X| >= 2、|Y| >= 1、およびXmin(1) + Xmin(2) + Ymax(1) > 1)

各テストは、線形時間と定数空間で実行できます (Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1)データがソートされていなくても、すべてを 1 回のパスで見つけることができます)。

于 2013-10-24T06:43:43.647 に答える
5

尋ねられる質問は、この InterviewBitの質問に似ています. あなたが求めたものと正確に一致するように、以下のソリューションにいくつかの変更を加えました。

次の 3 つの条件があります。

  • まず、合計が 1 ～ 2 の場合。
  • 第 2 に、合計が 2 より大きい場合、3 つのうち大きい方の要素が次の要素に置き換えられ、プロセスが繰り返されます。
  • 第 3 に、合計が 1 未満の場合、3 つの要素のうち小さい方の要素が次の要素に置き換えられ、同じプロセスが繰り返されます。
int Solution::solve(vector<float> &A) {
    if(A.size()<3) return 0;

    float a = A[0];
    float b = A[1];
    float c = A[2];

    for(int i=3;i<A.size();++i){
        if(a+b+c>1 && a+b+c<2)
            return 1;

        float temp = A[i];

        if(a+b+c>=2){
            if(a>b && a>c)
                a = temp;
            else if(b>c && b>a)
                b = temp;
            else
                c = temp;
        }
        else{
            if(a<b && a<c)
                a = temp;
            else if(b<c && b<a)
                b = temp;
            else
                c = temp;
        }
    }

    if(a+b+c>1 && a+b+c<2) return 1;

    return 0;
}

同じ問題は、2 ポインター手法を使用して解決することもできます。最初に、配列をソートする必要があります。ただし、その複雑さは O(logn) 以上になります。

int Solution::solve(vector<float> &A) {
    int n = A.size();

    if(n<3) return 0;
    sort(A.begin(), A.end());

    int l = 0, r = n-1;

    while(l<r-1){
        float s = A[l]+A[l+1]+A[r];
        if(s>=2)
            r = r-1;
        else if(s<1)
            l = l+1;
        else return 1;
    }
    return 0;
}
于 2020-06-14T12:20:32.667 に答える
-7

述べられているように、全体として問題は決定不可能です。これは、任意の 2 つの実数について、成立するかどうかを判断できないという事実によるものですa(bこの私の回答a > bも参照してください)。ただし、その問題を解決するには、実数と整数値を少なくとも 1 回比較する必要があります。整数と比較しても問題は簡単にはなりません。これは、2 桁目と 1 桁目の間に任意の数のゼロがある実数がある可能性があるためです。これは事前にはわかりません。そのような実数 (おそらくすべてではないかもしれませんが、それらの多く) をコンピューターのメイン メモリに格納することは、近似アルゴリズムで表すことができるため、そのような特定の実数にとっては大きな問題ではありません。2,00...001

詳細については、実関数の複雑性理論を読むことをお勧めします

于 2013-10-24T06:31:15.557 に答える