1

編集

要件の状態のピークを配列の端にすることはできないと指摘されました。

そこで、このサイトにたどり着きました

http://codility.com/

これにより、プログラミングの問題が発生し、2 時間で解決できれば証明書が発行されます。最初の質問は、私が以前に見たもので、通常、ピークとフラグの質問と呼ばれています。なじみがない場合

N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。ピークは、隣接する要素よりも大きい配列要素です。より正確には、それは次のようなインデックス P です。

0 < P < N − 1 および A[P − 1] < A[P] > A[P + 1]

. たとえば、次の配列 A:

A[0] = 1 
A[1] = 5 
A[2] = 3 
A[3] = 4 
A[4] = 3 
A[5] = 4 
A[6] = 1 
A[7] = 2 
A[8] = 3 
A[9] = 4 
A[10] = 6 
A[11] = 2

要素 1、3、5、および 10 の 4 つのピークがあります。

あなたは、相対的な高さが配列 A で表される一連の山脈に旅行に行く予定です。いくつの旗を持っていくかを選択する必要があります。目標は、特定のルールに従って、ピークにフラグの最大数を設定することです。

フラグはピークにのみ設定できます。さらに、K 個のフラグを使用する場合、任意の 2 つのフラグ間の距離は K 以上で​​ある必要があります。インデックス P と Q 間の距離は絶対値 |P − Q| です。

たとえば、上記の配列 A で表される山脈が N = 12 の場合、次のようになります。

2 つのフラグ。ピーク 1 と 5 に設定できます。

3 つのフラグ。ピーク 1、5、および 10 に設定できます。

フラグは 4 つですが、ピーク 1、5、および 10 の 3 つのフラグのみを設定できます。

したがって、この場合、最大 3 つのフラグを設定できます。

N 個の整数の空でないゼロ インデックスの配列 A を指定すると、配列の頂点に設定できるフラグの最大数を返す関数を作成します。たとえば、上記の配列が与えられた場合

上記で説明したように、関数は 3 を返す必要があります。

と仮定する:

N は [1..100,000] の範囲内の整数です。

配列 A の各要素は [0..1,000,000,000] の範囲内の整数です。

複雑:

予想される最悪の場合の時間計算量は O(N) です。予想される最悪の場合のスペースの複雑さは O(N) であり、入力ストレージを超えています (入力引数に必要なストレージは数えません)。

入力配列の要素は変更できます。

これは理にかなっていますが、このコードを使用して失敗しました

public int GetFlags(int[] A)
{
        List<int> peakList = new List<int>();
        for (int i = 0; i <= A.Length - 1; i++)
        {               
                if ((A[i] > A[i + 1] && A[i] > A[i - 1]))
                {
                    peakList.Add(i);
                }
        }

        List<int> flagList = new List<int>();
        int distance = peakList.Count;
        flagList.Add(peakList[0]);
        for (int i = 1, j = 0, max = peakList.Count; i < max; i++)
        {
            if (Math.Abs(Convert.ToDecimal(peakList[j]) - Convert.ToDecimal(peakList[i])) >= distance)
            {
                flagList.Add(peakList[i]);
                j = i;
            }
        }
        return flagList.Count;
}

編集

int[] A = 新しい int[] { 7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7 };

正解は 3 ですが、私のアプリケーションでは 2 と表示されています

4 つのピーク (インデックス 1、4、6、8) があり、そこから 2 つのピーク (1 と 6) にフラグを立てることができるはずなので、これはわかりません。

ここで何か不足していますか?明らかに、配列の最初または最後がピークになる可能性があるというのが私の仮定ですが、そうではありませんか?

これを Stack Exchange Programmers に入れる必要がある場合は移動しますが、ここでのダイアログが役立つと思います。

編集

4

4 に答える 4

0

ヒント: m 個のフラグを設定できる場合、少なくとも m * (m - 1) + 1 個の配列要素が必要です。N < 100,000 を考えると、上記をひっくり返すと、問題が効率的に力ずくで解決できるという確信が得られるはずです。

于 2013-10-18T21:49:52.947 に答える