問題タブ [array-algorithms]

配列を並べ替えて、並べ替えられた順序で各要素のインデックスを見つけたいと思います。たとえば、これを配列で実行すると、次のようになります。

私は得るだろう：

Javaでこれを行う簡単な方法はありますか？

n*n 要素の 2 次元配列があるとします。

• すべての行がソートされます
• すべての列がソートされます

例えば：

1 次元の並べ替えられた配列に変換します。よりも優れた解決策はありますかO(nlog(n))。

制約 :

1. O(1) スペース
2. 定刻

これは宿題の質問ではなく、私が出会った興味深い質問です。

ここに私が考えることができるいくつかの解決策がありますが、与えられた制約でそれを行うものは何もありません.

方法 1

*O(n)メモリ付き*

• 配列を再帰的に 2 つの部分に分割します。(各サブ問題のサイズが 2 以下になるまで分割を続けます)
• 配列を最初に、番号を最後に各サブ問題を並べ替えます。
• サブ問題配列をマージします

方法 2

O(n log n) 時間で

• 1234abcdになる辞書式順序に基づいて配列をソートします
• 配列 4321dcba の両方の半分を逆にします。
• 文字列全体を反転 abcd1234

方法 3

数値の範囲が定義されている場合

また、数値が特定の範囲内にある場合は、int say track= 0; を初期化できます。そして、配列内の数値に出くわしたときに適切なビットを設定します (例: (1 << a[2] ) 。1. アルファベットを配列の前半に入れ替えます。 2. トラック変数に数字をマークします。 3. 後で track を使用して配列の後半を埋めます。

方法 4 整数の範囲の制約を削除したい場合は、HashMap で方法 3 を使用できますが、より多くのメモリが必要になります。

O(1) 時間と O(n) 空間で一般的な問題を解決するより良い方法は考えられません。

ここでの一般的な問題とは、次のことを指します。

シーケンス x1y1x2y2x3y3....xnyn が与えられ、ここで x1 、 x2 はアルファベット x1 < x2 <.... < xn および y1y2...yn は integer です。y1 < y2 <.... < yn 出力を x1x2...xny1y2...yn として配置します

助言がありますか ？

整数のペアが与えられます(a1,b1),...,(an,bn)。と の場合、ペアはペアiによって「支配」されます。他のどのペアにも支配されていないペアのリストをすばやく決定するアルゴリズムは何ですか?jai < ajbi < bj

すべてのペアを確認できます。各ペアについて、すべてのペアをもう一度調べて、他のペアによって支配されているかどうかを確認します。このアルゴリズムは ordern^2です。n順序またはのアルゴリズムはありn log nますか?

次の2つのプロパティを持つリスト（少なくとも1つの正の整数を持つ）のサブリストを見つけようとしています1.その要素の合計が正です2.正の合計を持つ他のすべてのサブリストの最大長を持っています

私はそのリストの長さだけに興味があります。Kadaneのアルゴリズムは、O（n）時間で最大の合計を持つサブリストを見つけます。ここO（n）で同じことができるアルゴリズムはありますか？私は解決策を見つけましたが、それは実際にすべてのサブリストを計算し、もちろん非常に遅いです...。

お時間をいただきありがとうございます

N個の整数の配列を考えてみましょう。その要素の平均が与えられた数kよりも大きくなる（または等しくなる）ように、最も長い連続するサブ配列を見つけます。

明白な答えはO（n ^ 2）の複雑さを持っています。もっと上手くできますか？

次のことを理解するのに苦労しています:
String がありABRACADABRAます。これを例としてグループに分けます: Sはグループに分けられます:

S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...> where<>は配列を表し、S[i] はS位置の文字を表しますi。

私はそれを期待してS0=<S[0]S[4]S[8]S[11]>いましたが、私が読んだ本の「解決策」によると、S0=[ABR][ACA][DAB][RA]それは本質的にそうではありませんS[0]S[3]S[6]S[9]。
では、式の何を間違って読んでいるのS0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...>でしょうか?

重要な場合は、サフィックス配列で読んだ章からのものです。数式だけで困っています

このプログラムでは、ArrayList words. これまでのところ、 を使用してCollections.sort、テキスト ファイル内のすべての行をアルファベット順に配置しました。ただし、このプログラムに二分探索アルゴリズムを実装したいのですが、データのソート (マージ ソート、バブル ソートなど) なしでは実現できないと思います。私は間違っているかもしれませんが、それが私がガイダンスと知識のためにここに来た理由です.

次に、ソート用のメソッドを作成すると、これは a wordsis a Stringnot anString[]です。そのようなデータ型を使用してバブルソートを行うにはどうすればよいですか?

だから私はJavaに比較的慣れていないので（現在学校でAP Javaを取っています）、n * nボードを解決するための再帰アルゴリズムを開発しようとしています。送信している文字が単語であるかどうかなどを調べるために辞書を走査するためにすべて書き出されています。可能なすべての組み合わせを見つけるためにあらゆる方向に進みます。(n,p) で始まるすべての組み合わせが見つかったら、行の最後に到達するまで p をインクリメントし、n をインクリメントして p を 0 から再び開始します。（組み合わせは前後同じなので半分しか通らない）

私が問題を抱えている部分は、再帰シーケンスです。ボード上の特定の位置に移動したら、シーケンスの残りの部分で二度と移動しないようにマークしたいからです。それは完全には機能しません。誰かが理由を教えてくれたり、より良いアルゴリズムを書くのを手伝ってくれないかと思っていました。前もって感謝します

2 つの検索関数を考えてみましょう。

ルックアップ コストが低い関数はどれですか? それとも等しいですか？Lua はどのように連想配列を内部に格納しますか?