提醒一下大家,讨论归讨论,或者言辞有些偏激都可以理解.但请不要人身攻击,或者说脏话.


谢谢大家,请维护好论坛的日常秩序.

我真的很想知道。我跪求了。可怜可怜我吧。我真的没有别的办法来解决我的疑问。。我在这给各位跪下了。。在O(N)的时间，O(1)的空间里面找到第K大的数，。。。我问一下哦 O(N) 和 O(1) 是什么意思。。第k大的数。是什么样的数。？。我没猜错的话k应该是个整型变量吧。索性我就用数字100来假设。。假设k为100。将100代入原句。即。第100大的数。。第100是序数。含义为第100个某某。 第100个大的数。。倒底是怎样的一种数呢。求解

1,0(N)和0(1)是时间复杂度和空间复杂度,上网搜一下;
2,第K大的数,就是找序列号为K的数.

    举例,有这样 5 个数,原来是没排序的,经过排序后为 2,3,4,5,6.现在要找到第 3 大的数,也就是说 K=3,那么这个数值为 4 .

    但如果经过快排,显然时间复杂度要比楼主要求的要高,所以,只有利用快排的特性,找到第 K 大的数.《算法导论》第 108 页有详细论述。

----------------------------------------------------------------------------
我等代码等了很久了 ...          ~~~O(n)~~~
----------------------------------------------------------------------------

请问下我这个是 先建立一个单链表再赋值，最后用一个函数求最小值返回这点有没有问题？
至于满足你的复杂度，我还没考虑！

不是求最小值,而是求第 K 位数.

假设已经建立存好数据的带头结点单链表  

int find_k(link *head, int k)
{
    link *pos = head->next, *pos_k;
    int i = k, tmp;
   
    while (k--)
    {
        if ((pos->num) > (pos->next->num))
            {
                tmp = pos->num;
                pos->num = pos->next->num;
                pos->next->num = tmp;
            }
        pos = pos->next;
    }
    pos_k = pos;
   
    while (pos)
    {   
        if ((pos->num) < (pos_k->num))
            pos_k->num = pos->num;
        pos = pos->next;
    }
   
    return pos_k->num;
}

不知道满足楼主意思不 我是菜鸟

算法都出来了


怎么就没有个人能给我个我看的上眼的代码。。。


诶。。。

怎么才能让我不对你们绝望？