擅长:python、mysql、java
<p>是的,很好的拼图。我们可以从你说的话中找到中位数。</p>
<p>在C中,有1次出现max(k),3次出现次高,5次出现次高,以此类推</p>
<ol>
<li><p>如果我们对C的元素进行排序,则mth最高数左边的元素数是m^2(奇数和)</p></li>
<li><p>我们感兴趣的数字(计算中位数)
a、 如果n是奇数,则为(n^2+1)/2=alpha
b、 如果n是偶数,则alpha1=n^2/2和alpha2=n^2/2+1
但是alpha1=n^2/2从来不是一个正方形的数字=>;紧靠alpha1右侧的数字等于alpha1(前m个奇数的和是正方形的)=>;alpha1=alpha2。</p></li>
<li><p>所以它可以归结为确定m使得m^2(前m个奇数的和)刚好高于(n^2/2)</p></li>
<li><p>所以它可以归结为确定m=上限(n/sqrt(2))和原始序列中的mth最高数。(无论是m th最高还是(n-m-1)th最低都是优化)。</p></li>
<li><p>我们可以很容易地找到mth最高数(只需从左起注意m的第一个最大数)或使用中值算法在线性时间内完成它。</p></li>
</ol>