算法，用于从具有奇数个元素的数组中查找中值 [重复]
我想知道是否存在一种算法来寻找奇数长度数组的中值。显然，我们可以对数组进行排序，取中间值，但理想情况下，我们只需对中间值感兴趣，就可以在算法的时间复杂度方面获得收益。
如果没有这样的算法存在，任何关于如何着手开发这样一个算法的建议将是巨大的。
谢谢
共有3个答案
是的，存在一种算法。您讨论的问题是找到第k个最大元素，其中k是数组长度的一半1的值。这里有一个链接，指向一种在O（n）时间内完成此操作的方法，即中值。
您可以使用 Select 算法，该算法可以找到数组的第 k 个最小元素，其中 k 是数组大小的一半。
对于非结构化数据，它在O（n）中。
但请始终记住，理论的复杂性并不是一切！
也阅读这个问题。
这是通过选择算法解决的，并且可以在O（n）时间内完成。Quickselect或其细化内参选择是流行的方法。
quickselect的一个非常简短的总结是运行quicksort，但不是在每一步对两部分进行排序，而是只对包含要查找的元素的一半进行排序，这可以通过计算每个分区中有多少元素来确定。
例如，C实际上将其作为标准库函数：nth_element。
-
问题内容： 我被困在以下程序中： 我有一个输入整数数组，其中只有一个非重复数，例如{1,1,3,2,3}。输出应显示非重复元素，即2。 到目前为止，我执行了以下操作： 最好限制阵列中的解决方案。避免使用集合，地图。 问题答案： 由于几乎可以肯定这是一种学习练习，并且由于您非常接近正确完成它，因此需要进行以下更改才能使其正常工作： 将声明 __移到 外部循环 内部 -需要将标志设置为外部循环的每次迭
-
问题内容： 如何在数组中查找重复元素？我有一组电话号码，因此在电话号码中，我应该从右侧到左侧开始搜索，并找到相似的6个整数。那我应该把它们打印出来。 问题答案： 要查找重复项，可以按电话号码建立交叉引用，然后将其过滤为仅重复项。例如，考虑： 在Swift 4中，您可以使用以下命令构建交叉引用字典： 要么 然后，找到重复项： 显然，请使用对您有意义的任何模型类型，但是上面的模型使用以下类型： 有很多
-
问题内容： 查找整数数组中的第一个重复元素。 例如： 问题答案： 简单的解决方案是使用两个循环。外循环将遍历循环，内循环将检查元素是否重复，但此解决方案的时间复杂度为 o(n^2)。 另一种解决方案是创建另一个数组并对其进行排序。从原始数组中选取元素并使用二进制搜索在排序数组中查找元素，但此解决方案的时间复杂度为 o(n^logn)。 我们能做得更好吗？ 是的，我们可以从右到左迭代并使用HashS
-
本文向大家介绍JS查找数组中重复元素的方法详解，包括了JS查找数组中重复元素的方法详解的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了JS查找数组中重复元素的方法。分享给大家供大家参考，具体如下： JS的数据类型有一个数组。今天我们就来谈谈对数组的一种处理。相信很多人都遇到过从数组中查找出不重复的元素，但是我遇到的却是从数组中查找出重复的元素。 从js数组中查找出不重复的元素的方法有很多，
-
给定一个整数数组和一个整数m，我如何找到所有包含m个奇整数的子数组？如果我的问题不充分，下面是对整个问题的更长描述。这个问题有比n^2更快的解决方案吗？下面的解决方案似乎是n^2，我不确定如何进一步优化它。 https://github.com/cem3394/hr-haskell/blob/master/beautifulsubarrays.hs
-
问题内容： 我有一个多维数组，我想获取围绕该数组中特定元素的元素。 例如，如果我有以下内容： 如何找到以上任何一个元素中的所有8个元素？以及如何处理边缘的元素？ 我发现的一种方法是为此编写9行代码，这很明显，但是有更好的解决方案吗？ 问题答案： for (i = 0; i < array.length; i ) { for (j = 0; j < array[i].length; j ) { fo