編集
要件の状態のピークを配列の端にすることはできないと指摘されました。
そこで、このサイトにたどり着きました
これにより、プログラミングの問題が発生し、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 に入れる必要がある場合は移動しますが、ここでのダイアログが役立つと思います。
編集