問題タブ [array-algorithms]

左下隅の座標が (0,0) で右上隅が (n,n) の n 行 n 列のグリッドがあります。グリッド内のセルはすべて個別の値を持ち、私たちの目標はローカル ピークを見つけることです。これは、左、右、上、および下の隣接セルよりも大きい値を持つセルとして定義されます (つまり、斜めに隣接するセルは案件）。

問題は、そのセルにアクセスすることによってのみセルの値を確認できることです (つまり、(i,j) の値を確認するには、最初に (i+j) ステップを実行して (0,0) からそこに到達する必要があります)。 ）。O(n) ステップでローカル ピークを見つけるにはどうすればよいでしょうか。

Okay, so I need to devise the following algorithm (NO CODE NEEDED, just steps):

2 つのセットが与えられA、それぞれのB長さmがnで、各セットの数値が異なる、並べ替えられていない、およびm<n. どちらの結果にも重複する値がないように、2 つのセットの交差と和を計算します。アルゴリズムは O(mlog(n)) 時間で動作するはずです。

このような時間の複雑さを持つアルゴリズムを理解するのに本当に苦労しています。最初は、2 つの並べ替えられていない配列を連結し、それに対してマージ並べ替えを実行して重複を削除したかったのですが、それは割り当てられた複雑さをはるかに超えています。

配列は、ブルートフォース θ(n2) と比較して、アルゴリズム θ(nlogn) [ソート + 最小距離の検索] を作成して事前にソートされます。両方のコードは同じ仕事をしますが、最初のコードは制限時間を超えていることを示しています。エラーは何だろうと思います。コードにバグはありますか？

while ループを含むコード (制限時間超過)

for ループを使用するコード (うまく機能します)

x を空の配列のサイズとします。配列がいっぱいになると、長さが k > x の新しい配列が作成されます。古い配列の内容が新しい配列にコピーされ、新しい要素も格納されます。

• 長さ k の配列が k ステップで作成されます
• 要素のコピーには一定の時間がかかります。

質問: 各挿入操作が一定の時間を償却し、n 個の要素の挿入に Θ(n) かかるように、どのように k を選択しますか? 選択した結果、挿入操作ごとに一定の償却時間が得られるという仮定を、償却分析で証明してください。

私の直感では、k = 2*n は良いアイデアだと思いますが、それを証明する方法がわかりません。私は償却分析をまったく理解していなかったと思います。助言がありますか？

問題に遭遇したばかりで、これを解決する最善の方法は何かと考えていました。

リストのリストがあります

Lのサイズがnであると仮定すると、 Lにk回以上存在するすべての要素を見つける最良の方法は何でしょうか?

たとえば、 の場合k = 2、 を取得する必要があります [2, 3, 4, 6, 12]。

面接準備中。object-CIe input =[1,2,2,1,2,3,3,4] output =[1,2,1] を使用して、「配列から連続した重複を排除する最速の方法」という質問の解決策を見つけよう,2,3,4]

1. 配列内アプローチの場合: 配列内の要素をループします。要素 == 前の要素の場合は、それを削除し、他のすべての要素を再調整してステップを下げます。

2. 別の配列を使用できるアプローチの場合。要素 == 前の要素の場合、新しい「一意の配列」に追加しないでください。それ以外の場合は、一意の配列に追加します。

より良い解決策はありますか？コードは以下です。可能な最適化はありますか？

別の配列の使用

同じ配列の使用

MIT Intro to Algorithms クラスの Peak Finding Algorithm に出くわしました。1D と 2D の両方のケースで、アルゴリズムの実用的なアプリケーションにはどのようなものがあるのでしょうか? また、列のピークだけでなく、2D の場合に列のグローバルな最大値を見つけるのはなぜですか?