問題タブ [quickselect]

これは常に次の結果になりますか？

または、他の可能な結果は次のようになります。

私のマシンで何度も試してみたところ、n番目の値が常に連続していました。しかし、それは証拠ではありません;)。

目的:

一意の Kdtree を構築したいのですが、ベクターに重複があります。現在、中央値を見つけるために nth_element を使用しています。問題は、ベクトルを再度トラバースすることなく、一意の再構成可能な中央値を選択することです。中央値が連続している場合は、あまりトラバースせずに一意の中央値を選択できます。

私の新しいautocadフォームのボタンをクリックしてクイック選択ダイアログを表示する方法を知っている人はいますか?

SendStringToExecute メソッドを使用していますが、ダイアログを閉じた後にコマンドを送信します

上記のコードは機能しません。すべてのおかげで誰でも助けることができます

私はquickSelectアルゴリズムを理解して実装するためにquickSelectに従いました。ここでよくわからないことが 1 つk-pivotありpivot-first+1ます。

私の実装はこのリンクとまったく同じですが、機能していません。

出力:

整数配列を指定すると、90 パーセンタイルは、配列の 90% を超える最初の数値です。より具体的な定義が必要な場合は、http://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex6def.htmlをご覧ください。

通常の状況で正常に動作するクイック選択プログラムを作成しました。それは、90パーセンタイルが含まれる側だけをソートする部分ソートです。

ただし、すべての整数が同じで、90 パーセンタイルがない場合などの特別な場合には、90 番目の数値は検索されますが、-1 は返されません。

修正後、プログラムが O(n) であることを確認してください。

(k-1) 番目の数値と k 番目の数値を比較するためにクイック セレクト関数を繰り返し呼び出すメイン関数でループを使用した場合、実行時間は (nk)*n=O(n^2) になります (クイック セレクトは O (n) googled) 選択中に有効な 90 番目の数字を簡単に見つける方法はありますか?

リスト内の m 番目に小さい数値を見つけるために、クイック選択を実装しようとしました。プログラムを実行すると、同じ配列で正しい値が返されることもあれば、間違った値が返されることもあります。私は何を間違っていますか 彼女はコードです

これは、アルゴリズムが失敗する入力です。

上記のステートメントを繰り返し実行すると、5 (正しい) と 4 (正しくない) が交互に表示されます。

私を特に困惑させることの 1 つ (私は Python を初めて使用します) は、同じ入力を繰り返したときに関数の戻り値が異なる理由です。かなり散発的に見えます..ところで、私はJupyterを使用しています

配列内の n 個の最小項目を判別するコードを作成しようとしています。私がこれに苦労しているのは悲しいことです。昔の私の大学の教科書のアルゴリズムに基づくと、これは正しいように見えます。ただし、スタックオーバーフロー例外が発生するため、明らかに何か間違っています。

私のアプローチは次のとおりです。

1. ピボットを start + (end-start) / 2 に設定します (オーバーフローを防ぐために start+end/2 ではなく)
2. この場所の整数を使用して、すべてを比較するピボットにします
3. このピボットの周りのすべてを繰り返し交換して、物事がソートされるようにします（ピボットを基準にしてソートされます）
4. n == ピボットの場合、完了したと思います
5. それ以外の場合、たとえば 4 つの最小要素が必要でピボットが 3 の場合、右側 (または 2 番目に小さい要素が必要な場合は左側) を見る必要があります。

-

編集：有効な質問に反対票を投じる場合は、少なくとも理由をコメントしてください。

まず第一に、これは学校の課題であり、指導を求めているだけです。

私の仕事は、quickselect を使用して、seq 内の k 番目に小さい要素を見つけるアルゴリズムを作成することでした。これは簡単なはずですが、いくつかのテストを実行しているときに壁にぶつかりました。何らかの理由で入力を使用する(List(1, 1, 1, 1), 1)と、無限ループに入ります。

これが私の実装です：

なんらかの理由で (または疲れているため)、間違いを見つけることができません。誰かが私がどこで間違っているかを教えてくれたら、私は喜んでいます.

入力が適度に大きい場合でも、中央値の中央値クイック選択アルゴリズムがセグメンテーション違反を引き起こすコードの障害を見つけるのに苦労しています。出力を取得すると、出力は正しいです。以下は、指定されたテスト パラメーターを使用してシステムで segfault を引き起こす完全なコードです。