中位数
我已经阅读了阶数统计，以在线性时间O（n）中找到大小为n的数组中的第k个最小（或最大）元素。
有一步需要找到中位数。
- 将数组拆分为 [n/5] 部分。每个部分有 5 个元素。
- 找到每个部分的中位数（我们现在有[n/5]个数字）
- 重复步骤 1 和 2，直到我们只有最后一个数字。（即递归）
T（n）=T（n/5）O（n），我们可以得到T（n）＝O（n）。
但是，如果我们有一个大的数组，我们最终得到的数字不是中位数，而是中位数的中位数。
请考虑一个有125个元素的数组。
首先，它被分成25部分，我们找到25个中间值。然后，我们把这25个数字分成5部分，找出5个中位数，最后，我们得到的数字就是中位数的中位数。(非中位数)
我关心它的原因是，我可以理解最多有[3/4]*n个元素比中间值小（或大）。但如果不是中位数而是中位数的中位数呢？在更糟糕的情况下，必须有比枢轴更小（或更大）的元素，这意味着枢轴更接近数组的边界。
如果我们有一个非常大的数组，我们找到它的中间值的中间值的中间值的中间值的中间值。在最坏的情况下，我们找到的支点仍然可以非常接近界限，在这种情况下的时间复杂度是多少？
我建立了一个包含125个元素的数据集。结果是9吗？
0.8 0.9 1 inf inf
1.8 1.9 2 inf inf
6.8 6.9 7 inf inf
inf inf inf inf inf
inf inf inf inf inf
2.8 2.9 3 inf inf
3.8 3.9 4 inf inf
7.8 7.9 8 inf inf
inf inf inf inf inf
inf inf inf inf inf
4.8 4.9 5 inf inf
5.8 5.9 6 inf inf
8.8 8.9 9 inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
其中inf表示数量足够大。
共有1个答案
让我们来表示你的中位数的中位数...as[的中值]* = M。
首先，我相信中位数算法(选择一个好的支点)不是递归的。算法如下:
- 将元素拆分为 5 个组
- 查找每组的中位数
- 找到中位数的中位数并将其用作枢轴。
中位数将小于3n/10个元素，大于另一个3n/10个元素，而不是3n/4。选择中位数后，您有n/5个数字。中位数大于/小于这些数字的一半，即n/10。这些数字中的每一个本身都是中位数，因此它大于/小于2个数字，因此您又得到了2n/10个数字。现在总共，您得到n/10 2n/10=3n/10个数字。
为了解决第二个问题，在收集示例数据集中的5个组并计算它们的中间值后，我们将有以下顺序：
1, 2, 7, inf, inf
3, 4, 8, inf, inf
5, 6, 9, inf, inf,
inf, inf, inf, inf, inf,
inf, inf, inf, inf, inf.
所以中位数确实是9。
您建议的 [中位数] * 算法的运行时将为：
T(n) = O(n * log(n))
现在让我们尝试分析我们有多少个小于/大于M的数字。我们有以下小组：
- 深度 1：n/5 个元素，所有中位数
- 深度 2：n/25 个元素，所有中位数
- ...
- 深度 i： n/（5^i） 元素所有中位数
每个组小于/大于前一个深度的 2 个元素，即小于/大于前一个深度的 2 个元素，依此类推：
计算总和，我们得到我们的M大于/小于（n * （2^k） k * n） /（（2^k） * （5^k））。对于深度 = 1，您将获得中位数的中位数，即 3n/10。
现在假设深度为[log_5（n）]，即n=5^k，我们得到：
5^k *(2^k)/(5^k国王* 2^k)这是-
-
关于中位数的算法，有一点我不明白。这个算法的一个关键步骤是找到一个近似的中位数，根据维基百科，我们保证这个近似的中位数大于初始集元素的30%。 为了找到这个近似中位数，我们计算每组5个元素的中位数，将这些中位数聚集在一个新的集合中，然后重新计算中位数，直到获得的集合至少包含5个元素。在这种情况下，我们得到集合的中值。（如果我的解释不清楚，请参阅维基百科页面。） 但是，请考虑以下125个元素: 因此
-
我需要得到一个32位数字中的1位数字，其中只有一个1位（总是）。在C++或ASM中最快的方法。 例如
-
下面代码中编写的方法需要取整数以及整数中第一位和最后一位的结果和。 注意：虽然我知道正确的解决方案，但我问这个问题的原因是我需要了解为什么我的代码不起作用，因为这使我成为一名更好的程序员，请帮助。 在上面的代码中，如果我在if块之后保持number/=10，如下所示 然后我的代码给出了正确的结果。例如，如果我在方法中输入121，因为第一个数字是1，第二个数字是1，那么它将两者相加，并给出结果2。这
-
NowCoder 题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 解题思路 // java /* 大顶堆，存储左半边元素 */ private PriorityQueue left = new PriorityQueue<>((o1, o2) ->
-
问题内容： 如何使用分布式方法，IPython和Spark查找整数的整数中位数？该元素约为700,000个元素，因此太大而无法收集和找到中位数。 使用Scala答案的思想，我试图用Python编写类似的答案。 我知道我首先要排序。我不知道怎么。我看到了（按给定的RDD排序）和（按假定的（key，value）对组成的this排序）。我认为两者都使用键值，而我只有整数元素。 首先，我在想做什么？ 接下
-
问题内容： 我在Redis上使用Lua，想比较两个带符号的64位数字，这些数字存储在两个8字节/字符的字符串中。 如何使用Redis中可用的库进行比较？ http://redis.io/commands/EVAL#available- libraries 我想知道并检查。我认为这可能涉及为每个64位int提取两个32位数字，并对它们进行一些巧妙的数学运算，但是我不确定。 我有一些代码可以使这一过程