6

マグニチュードポール：左側の要素がそれ以下であり、右側の要素がそれ以上である配列内の要素。

入力例

3,1,4,5,9,7,6,11

希望する出力

4,5,11

インタビューでこの質問をされたので、要素のインデックスを返し、条件を満たした最初の要素のみを返す必要があります。

私の論理

  1. 2つのMultiSet（重複も考慮できるように）を取ります。1つは要素の右側用で、もう1つは要素（極）の左側用です。
  2. 0番目の要素から始めて、残りのすべての要素を「正しいセット」に入れます。
  3. この0番目の要素が「右セット」のすべての要素以下の場合の基本条件は、そのインデックスを返します。
  4. それ以外の場合は、これを「左セット」に入れ、インデックス1の要素から開始します。
  5. 配列をトラバースし、毎回「左セット」から最大値を選択し、「右セット」から最小値を選択して比較します。
  6. 任意の要素の任意の時点で、その左側のすべての値は「左のセット」にあり、その右側の値は「右のセット」にあります

コード

int magnitudePole (const vector<int> &A) {  
   multiset<int> left, right;        
   int left_max, right_min;          
   int size = A.size();
   for (int i = 1; i < size; ++i)
       right.insert(A[i]);
   right_min = *(right.begin()); 
   if(A[0] <= right_min)
       return 0;
   left.insert(A[0]);
   for (int i = 1; i < size; ++i) {
       right.erase(right.find(A[i]));
       left_max = *(--left.end());
       if (right.size() > 0)
           right_min = *(right.begin());
       if (A[i] > left_max && A[i] <= right_min)
           return i;
       else
           left.insert(A[i]);
   }
   return -1;
}

私の質問

  • ロジックが正しくないと言われましたが、なぜこのロジックが正しくないのか理解できません（いくつかのケースをチェックして、正しいインデックスを返していますが）
  • 私自身の好奇心のために、O（n）時間でセット/マルチセットを使用せずにこれを行う方法。
4

8 に答える 8

9

O（n）アルゴリズムの場合：

  1. [0、length（n））のすべてのkについてn[0]からn[k]までの最大の要素を数え、答えを配列maxOnTheLeftに保存します。これにはO（n）がかかります。
  2. [0、length（n））のすべてのkについてn[k]からn[length（n）-1]までの最小要素を数え、答えを配列minOnTheRightに保存します。これにはO（n）がかかります。
  3. 全体をループして、maxOnTheLeft <= n [k]<=minOnTheRightのn[k]を見つけます。これにはO（n）の費用がかかります。

そして、あなたのコードは（少なくとも）ここでは間違っています：

if (A[i] > left_max && A[i] <= right_min) // <-- should be >= and <=
于 2013-03-13T22:26:06.413 に答える
3
  • NorthPoleとSouthPoleという2つのbool[N]を作成します（ユーモラスに）。
  • これまでに見つかった最大要素を追跡するA[]を進め、A [i]> Max（A [0..i-1]）の場合はSouthPole[i]をtrueに設定します。
  • A []を逆方向に進み、A [i] <Min（A [i + 1..N-1）の場合、NorthPole[i]をtrueに設定します。
  • NorthPoleとSouthPoleを進めて、両方がtrueに設定されている最初の要素を見つけます。

上記の各ステップのO（N）は、各ノードに1回アクセスするため、全体としてO（N）になります。

于 2013-03-13T22:28:56.570 に答える
3

Javaの実装：

Collection<Integer> magnitudes(int[] A) {
    int length = A.length;
    // what's the maximum number from the beginning of the array till the current position
    int[] maxes = new int[A.length];
    // what's the minimum number from the current position till the end of the array
    int[] mins = new int[A.length];

    // build mins
    int min = mins[length - 1] = A[length - 1];
    for (int i = length - 2; i >= 0; i--) {
        if (A[i] < min) {
            min = A[i];
        }
        mins[i] = min;
    }

    // build maxes
    int max = maxes[0] = A[0];
    for (int i = 1; i < length; i++) {
        if (A[i] > max) {
            max = A[i];
        }
        maxes[i] = max;
    }

    Collection<Integer> result = new ArrayList<>();
    // use them to find the magnitudes if any exists
    for (int i = 0; i < length; i++) {
        if (A[i] >= maxes[i] && A[i] <= mins[i]) {
            // return here if first one only is needed
            result.add(A[i]);
        }
    }
    return result;
}
于 2013-10-03T07:27:40.190 に答える
1

あなたのロジックは完全に正しいようで（実装をチェックしていませんが）、O（n）時間アルゴリズムを与えるように実装できます！セットの観点から考えるといい仕事です。

右のセットは最小値をサポートするスタックとして実装でき、左のセットは最大値をサポートするスタックとして実装できます。これにより、O（n）時間アルゴリズムが得られます。

max / minをサポートするスタックを持つことは、よく知られているインタビューの質問であり、各操作で実行できます（push / pop / min / maxはO（1）です）。

これをロジックに使用するには、擬似コードは次のようになります。

foreach elem in a[n-1 to 0]
    right_set.push(elem)

while (right_set.has_elements()) {
   candidate = right_set.pop();
   if (left_set.has_elements() && left_set.max() <= candidate <= right_set.min()) {
       break;
   } else if (!left.has_elements() && candidate <= right_set.min() {
        break;
   }
   left_set.push(candidate);
}

return candidate
于 2013-03-13T22:39:34.013 に答える
1

Codilityでこの問題を確認し、Perlで解決しました。

sub solution {
        my (@A) = @_;            

        my ($max, $min) = ($A[0], $A[-1]);
        my %candidates;

        for my $i (0..$#A) {
                if ($A[$i] >= $max) {
                        $max = $A[$i];
                        $candidates{$i}++;
                }
        }
        for my $i (reverse 0..$#A) {
                if ($A[$i] <= $min) {
                        $min = $A[$i];
                        return $i if $candidates{$i};
                }
        }
        return -1;
}
于 2013-05-04T19:07:36.167 に答える
0

次のコードはどうですか？最悪の場合、効率は良くないと思いますが、期待される効率は良いでしょう。

    int getFirstPole(int* a, int n)
{
    int leftPole = a[0];
    for(int i = 1; i < n; i++)
    {
        if(a[j] >= leftPole)
        {
            int j = i;
            for(; j < n; j++)
            {
                if(a[j] < a[i])
                {
                    i = j+1;  //jump the elements between i and j                   
                    break;
                }
                else if (a[j] > a[i])
                    leftPole = a[j];
            }
            if(j == n) // if no one is less than a[i] then return i
                return i;
        }
    }
    return 0;
}
于 2013-03-13T23:51:01.193 に答える
0
  1. と呼ばれるintの配列とmags、と呼ばれるint変数を作成しますmaxMag。
  2. ソース配列の各要素について、要素が。以上であるかどうかを確認しmaxMagます。
  3. の場合：mags配列に要素を追加し、を設定しmaxMag = elementます。
  4. そうでない場合：mags配列をループして、すべての要素を削除します。

結果：マグニチュードポールの配列

于 2013-03-29T22:23:26.330 に答える
0

興味深い質問ですが、私は以下に示すC＃で独自のソリューションを持っています。コメントを読んで、私のアプローチを理解してください。

public int MagnitudePoleFinder(int[] A)
{
    //Create a variable to store Maximum Valued Item i.e. maxOfUp
    int maxOfUp = A[0];

    //if list has only one value return this value
    if (A.Length <= 1) return A[0];

    //create a collection for all candidates for magnitude pole that will be found in the iteration
    var magnitudeCandidates = new List<KeyValuePair<int, int>>();

    //add the first element as first candidate
    var a = A[0];
    magnitudeCandidates.Add(new KeyValuePair<int, int>(0, a));

    //lets iterate
    for (int i = 1; i < A.Length; i++)
    {
        a = A[i];
        //if this item is maximum or equal to all above items ( maxofUp will hold max value of all the above items)
        if (a >= maxOfUp)
        {
            //add it to candidate list
            magnitudeCandidates.Add(new KeyValuePair<int, int>(i, a));
            maxOfUp = a;
        }
        else
        {
            //remote all the candidates having greater values to this item
            magnitudeCandidates = magnitudeCandidates.Except(magnitudeCandidates.Where(c => c.Value > a)).ToList();
        }
    }
    //if no candidate return -1
    if (magnitudeCandidates.Count == 0) return -1;
    else
        //return value of first candidate
        return magnitudeCandidates.First().Key;
}
于 2014-02-25T15:22:34.390 に答える