問題タブ [array-algorithms]

私はこの擬似コードを持っています:

私はそれを次のように解釈します：

ただし、それはスキップしunsortedArr[0]ます。つまり、機能しません。

2番目を次のように変更forします。

意図したとおりに実行します。疑似コードに誤りがあるのでしょうか、それとも私の最初の解釈の試みが間違っていたのでしょうか?

私は初心者です。組織化されていないことをお許しください。さて、私がしたことは、8 から 100 までのすべての素数で満たされた配列を作成することでした。ここでやりたいことは、101 から 200 までのすべての素数を見つける別の配列を作成することです。それでは、最初の部分をどのように行ったかを説明させてください。

//Prime1 は、8 から 100 までのすべての素数を格納する動的な整数配列です

ここで主な問題に戻ります。「if(primeTest % "prime#" !=0)」と書くのではなく、Prime1 配列全体でモジュラスを使用して、すべての値がゼロに等しくないかどうかを確認できるようにしたいと考えています。詳しく説明しましょう。

//中かっこの欠落はご容赦ください

^^ここで、101 から始まる値を取得し、Prime1 配列の最初の値でモジュラスを計算します。ご存知のように、11 (配列内の最初の素数) は、素数ではない数でも true を示す可能性があるため、これは誤検出を引き起こす可能性があります。これが、配列内のすべての値で数値をテストして、他の素数で割り切れないことを確認できるようにする必要がある理由です (素数であることを意味します)。

1 回の反復で、並べ替えられていない配列の 2 番目に最大の要素が必要です。例: 配列は 3 9 8 2 0 -4 87 45 3 2 1 0 です。答えは 45 である必要があります。1 回の反復で max 要素を見つけるのは非常に簡単ですが、同じ反復で 2 番目の max を見つける方法、または定数時間配列のフォート反復の後。

M個のソートされた整数配列の中央値を見つける方法は? 各配列のサイズは N によって制限されます。各配列には、並べ替えられた整数要素が含まれていると仮定します。

この質問には 2 つのバリエーションがあります。

1. 各配列は同じサイズです。
2. 各配列のサイズは異なります。

n 個の数値を入力し、それらを変数に格納して、後で処理できるようにする必要があります。制約: 1. 連続する入力間の任意の数のスペース。2. 入力の数は不明です。3. 入力セットは 256KB を超えてはならず、0<= i <=10^18 の間である必要があります

最近、コーディングの問題に取り組みました。次の問題の解決策を思いつきました。

N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。配列 A は、テープ上の数字を表します。
0 < P < N のような任意の整数 P は、このテープを 2 つの空でない部分 A[0]、A[1]、...、A[P − 1] および A[P]、A[ に分割します。 P + 1]、...、A[N − 1]。
2 つの部分の違いは次の値です: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + .. . + A[N − 1])|
つまり、最初の部分の合計と 2 番目の部分の合計の絶対差です。
たとえば、次のような配列 A を考えます。
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
このテープを 4 つの場所に分割できます。
P = 1、差 = |3 − 10| = 7
P = 2、差 = |4 − 9| = 5
P = 3、差 = |6 − 7| = 1
P = 4、差 = |10 − 3| = 7

関数を書きます: function solution(A);
これは、N 整数の空でないゼロ インデックスの配列 A が与えられると、達成できる最小の差を返します。
たとえば、次の場合:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
上記で説明したように、関数は 1 を返す必要があります。
N は [ 2..100,000
] の範囲内の整数です。
配列 A の各要素は [−1,000..1,000] の範囲内の整数です。

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

以下は、ソリューションのテストから得たフィードバックです。

正確性: small_range レンジ シーケンス、長さ = ~1,000 1.900 秒
RUNTIME ERROR テスト済みプログラムが予期せず終了
パフォーマンス: 検出された時間の複雑さ: O(N * N)

そのため、1000 前後の範囲で 1 つの実行時エラーが発生しています。そして最も重要なことは、O(n) を取得していないことです。ネストされた for ループを使用しているため、O(n * n) を取得しています。

(1) 実行時エラーを修正するにはどうすればよいですか?
(2) 同じ問題に対して O(n) アルゴリズムをどのように構築できますか? 助言がありますか？

これが私の解決策です：

ソートされていない実数の配列を線形時間でソートできますか? これは私が考えていることです：

サイズ n のソートされていない配列が与えられた場合:

• 選択アルゴリズムを使用して要素を見つけsqrt(n)^thます (x と呼びます): O(n)
• x よりも小さい要素と x よりも大きい要素を見つけて、2 つの配列を形成します: O(n)
• 2 つの配列を別々に並べ替える: O(sqrt(n)log(sqrt(n))) = O(n) as log(n) < sqrt(n)

したがって、アルゴリズム全体は O(n) です

下限が nlog(n) であることはわかっています。私は何を間違っていますか？

このプログラムはコンパイル時にエラーを表示しています。何が問題なのか教えていただけますか?

メインクラス:

ソートクラス:

例外。

アルゴリズムに関する提案も歓迎しますが、プログラムの本質を維持することを好みます。

「アルゴリズム分析」の課題に取り組んでいますが、明日提出しなければならないこの質問に行き詰まっています。助けが必要です。解ける方回答お願いします。

n 個の数値の配列 A が与えられた場合、その配列で最も頻繁に発生する要素 (その配列のモード) を見つける効率的なアルゴリズムを記述します。また、アルゴリズムの時間の複雑さを分析します。