問題タブ [array-algorithms]

ソートされた整数の配列があります。数値が与えられた場合、最悪の場合でも O(logn) でその数値の出現回数を見つける方法。

二分木の場合、1 つの垂直線に含まれるすべてのノードの合計を取得したいと考えています。各頂点ノードのノードの合計が必要です

ティーの上を見ると

次のアルゴリズムを実装しました

1. 上記のアルゴリズムは問題ないと思います。確認できる人はいますか?
2. また、HashMap、arraylist、またはJavaのそのようなコレクションデータ型を使用せずにそれを行うにはどうすればよいですか。配列のサイズがどうなるかわかりません。
3. 1 つのアプローチは、二重リンク リストを使用し、必要に応じて左右の移動にノードを追加することです。このアプローチをどのように実装できますか? 他の単純な/より時間効率の良いアプローチはありますか?
4. 上記のコードの複雑さは O(n) ですか? （時間の複雑さを分析するのが苦手なので、質問します）

float または int を文字列に変換するアルゴリズムを実装するにはどうすればよいですか? リンクを 1 つ見つけました http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-0-2-years-about-algorithms-13

しかし、そこに与えられたアルゴリズムを理解できません

N 個の整数のソートされていない配列と、値が 'k' である次の要素のインデックスを返す関数getNextIndexOf (int k) が与えられた場合、最後の要素 (つまり、インデックス N) を最も少ない呼び出し回数で取得するにはどうすればよいでしょうか? getNextIndexOf (int k) へ?

*つまり、 m^番目の呼び出しが「N」を返し、mができるだけ小さくなるように、どの値 k ₁、k ₂、...、k _mで getNextIndexOf(int k) を呼び出す必要がありますか?

**編集: getNextIndexOfは、返された最後のインデックスを追跡できると想定できます
(たとえば、C の静的ローカル変数のように)。最初の呼び出しでは、引数 (int k) に等しい最初の要素のインデックスを返します。

私には問題があり、OKっぽい解決策があります。私はそこにもっと良い解決策があることを望んでいます。

問題

約200,000個の整数の配列があります。2つのインデックスi1とi2が与えられた場合、i1とi2の間のすべての要素の合計を計算する必要があります。配列内の各整数は1から4までです。例えば：

この操作は約20万回実行されるため、かなり高速である必要があります。forループの単純なカウンターはO（n）であり、遅すぎます。アレイは構築後に変更されることはないため、比較的高価な前処理段階があっても問題ありません。

これまでの私の最善の解決策

このアルゴリズムはO（log n）時間で機能します。

最初に、元の配列の長さが2の累乗になるまで、元の配列にゼロを埋め込みます。次に、配列を2つの等しい部分に分割し、それぞれの合計を格納します。次に、配列を4分の1に分割し、それぞれの合計を格納します。それから8分の1。配列が2要素の長さのセクションに分割されるまでこれを続けます。上記の8要素配列の場合、これには2つの手順が必要です。

次に、2つのインデックスが与えられると、O（log n）時間でsubsection_sumを計算できるようになります。たとえば、subsection_sum（a、2、7）== Quarters [1] +halves[1]です。

1 行に 1 単語の単語を含むファイルを考えてみましょうN。ファイルが大きすぎるため、ファイル全体を一度にメモリに読み込むことができません。 私の答え：ファイルを.So
に分割します各チャンクのサイズ一度に 1つのチャンクをメモリに読み込み、ソートしてファイルに書き戻します.すべてのkチャンクをソートします. を実行します。 合計時間の複雑さを分析します。どうすればできますか？ 各チャンクのソートにかかる時間 = (クイックソートを使用すると仮定) k 個のチャンクをマージする時間 = (それは??) したがって、総時間の複雑さ = 時間の複雑さを分析する週k chunksx = N/k

k way merge

xlogx
klogk
??

アルゴリズムについて 1 つ質問があります。私はこれに関するアルゴリズムを書くように頼まれました: 私のためにアルゴリズムを書くようにあなたに頼むのではなく、私がする必要がある効率的なプロセスを教えてください:

本や聖書の内容のような n 個の要素の配列があり、その中に入力文字列「Gaurav Agarwal」を挿入したとします。あなたがしたいことは、その文字列の配列に存在する一意の要素を取得する必要があります。どのように先に進むかのアルゴリズム (未ソート)

あなたが理解していない場合は、私に知らせてください.

属性xとyを持つオブジェクトの膨大なリストが与えられます。両方の属性の特定の上限と下限の間にあるすべてのオブジェクトを検索する必要があります。

これを実装するための効率的なアルゴリズムがあるかどうか疑問に思いました。

ありがとう！

ソートされた整数の配列が与えられた場合、合計が K になる整数のペアを見つけるにはどうすればよいでしょうか?

例: array = 1,3,5,6,10、K = 6答えは 1 と 5 です。

時間の複雑さは最小限に抑える必要があります。

QMLファイルブラウザを作成しています。ここで、 backおよびforward関数を実装したいと思います。この機能は、ブラウザの前後の機能に似ています。例 ：

「/home/ text / folder1」から始めて、「/ home / text / folder1/src」を参照します。ここで、「/ home / text / folder1 / src/java」を参照します。2回押すと、「/ home / text / folder1」になり、もう押すことができなくなります（ボタンがグレー表示されるか、他の方法で、表示される「前の」アイテムがなくなったことを示します）。 ）。

私はこれを二重リンクリストを介して実装することを考えていました。しかし、リストのどこに新しいアイテムを挿入すべきか、いつ挿入すべきかを理解するのに苦労しています。

前の例を見てください：2回押す代わりに、1回だけ押し戻す場合（現在は「/ home / text / folder1 / src」にいます）。突然「/home/ text / folder2」に移動した場合、今はどうなりますか？私の二重リンクリストは今どのように見えるべきですか？

これはデータ構造の問題であり、実装ではないため、コードは必要ありません。