问题标签 [quickselect]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
201 浏览

c++ - 使用 std::nth_element 时,第 n 个元素的重复项是否总是连续的?

这是否总是会导致:

或者其他可能的结果是:

我已经在我的机器上尝试了多次,导致第 n 个值始终是连续的。但这不是证据;)。

它的用途:

我想构建一个独特的 Kdtree,但我的向量中有重复项。目前我正在使用 nth_element 来查找中值。问题是选择一个唯一/可重构的中位数,而不必再次遍历向量。如果中值是连续的,我可以选择一个唯一的中值,而无需太多遍历。

0 投票
2 回答
463 浏览

c# - AutoCAD C#从我的新表单中调用快速选择对话框

有谁知道如何通过单击我的新 autocad 表单上的按钮来显示快速选择对话框。

我使用 SendStringToExecute 方法,但它在关闭对话框后发送命令

上面的代码不起作用,任何人都可以帮助感谢所有人

0 投票
2 回答
259 浏览

c - quickSelect 算法返回第 k 个最小元素

我按照quickSelect来理解和实现 quickSelect 算法。我不确定的一件事是:他们为什么这样做k-pivot并且pivot-first+1

尽管我的实现与此链接完全相同,但它不起作用。

输出 :

0 投票
0 回答
992 浏览

c - 如何使用快速选择查找第 k 个百分位数

给定一个整数数组,第 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)我用谷歌搜索)。在选择时找到有效的第 90 个数字是否更简单?

0 投票
1 回答
1046 浏览

python - python中快速选择的实现。函数不稳定并返回不同的值

我尝试实现快速选择以在列表中找到第 m 个最小的数字。当我运行程序时,它有时会在同一个数组上返回正确的值,而有时会返回不正确的值。我做错了什么她是代码

这是算法失败的输入。

当我反复执行上述语句时,我交替得到 5(正确)和 4(不正确)。

让我特别困惑的一件事(我是 python 新手)是为什么我在使用相同的输入重复时得到不同的函数返回值。看起来相当零星..顺便说一句,我正在使用 Jupyter

0 投票
2 回答
292 浏览

java - 快速选择实现不起作用

我正在尝试编写代码来确定数组中的 n 个最小项。很遗憾我正在为此苦苦挣扎。根据我当年大学教科书中的算法,这看起来是正确的。但是,显然我做错了什么,因为它给了我一个堆栈溢出异常。

我的做法是:

  1. 将枢轴设置为 start + (end-start) / 2 (而不是 start+end/2 以防止溢出)
  2. 使用此位置的整数作为我比较所有内容的基准
  3. 围绕该枢轴迭代和交换所有内容,以便对事物进行排序(相对于枢轴排序)
  4. 如果 n == pivot,那么我想我已经完成了
  5. 否则,例如,如果我想要 4 个最小的元素并且枢轴是 3,那么我需要查看右侧(如果我想要第二个最小的元素,则需要查看左侧)。

-

编辑:如果您要对有效问题投反对票,请至少评论一下原因。

0 投票
1 回答
196 浏览

arrays - 使用外部函数查找未排序数组中的第 k 个元素

我需要设计一个算法,使用名为“MED3”的函数在未排序的数组中找到第 k 个最小元素:此函数查找数组的 n/3(地板)和 2n/3(天花板)元素(如果已排序) (与中位数非常相似,但不是 n/2 它返回这些值)。

我考虑过围绕这两个值进行分区,而不是像 QuickSelect 那样继续,但问题是“MED3”不返回两个值的索引,只返回值。

例如,如果数组是:1、2、10、1、7、6、3、4、4,则返回 2(n/3 值)和 4(2n/3 值)。

我还想过遍历数组并将 2 到 4 之间的所有值(例如,在上面的给定数组中)放入新数组,然后再次使用“MED3”,但可以重复(如果数组为 2, 2, 2, 2, ..., 2 我每次都会取所有元素)。

有任何想法吗?我必须使用“MED3”。* MED3 就像一个黑匣子,它以线性时间运行。

谢谢你。

0 投票
0 回答
26 浏览

c - 使用快速选择从文件中读取的排序浮点数会导致分段错误

我必须使用快速选择来排序和写入数组的前 N ​​个元素并将它们写在文本上。

问题在于输入文件和我尝试从中读取的数据量。

我使用一个常数 N 来定义我想从文件中读取的最大数量,但到目前为止它只从文件中读取和排序多达 194 个元素。不过,我应该可以用 1000 万美元来做到这一点。

这是代码:

如果我尝试定义 N=195 或更多,则代码不起作用。

0 投票
1 回答
68 浏览

scala - 使用 `quick-look` 查找特定元素

首先,我想说这是一个学校作业,我只是寻求一些指导。

我的任务是编写一个算法,使用快速选择找到序列中的第 k 个最小元素。这应该很容易,但是在运行一些测试时我碰壁了。出于某种原因,如果我使用输入(List(1, 1, 1, 1), 1),它会进入无限循环。

这是我的实现:

由于某种原因(或因为我累了),我无法发现我的错误。如果有人能提示我哪里出错了,我会很高兴。

0 投票
1 回答
325 浏览

c++ - 为什么我的中位数快速选择算法段错误?

我很难在我的代码中找到导致我的中位数快速选择算法在输入甚至中等大时出现段错误的错误。当我得到输出时,输出是正确的。以下是使用给定测试参数在我的系统上导致段错误的完整代码。