消息关闭
    暂无新消息!
如题,不排序找第k大的数该怎么写?

3个回答

︿ 2

int getNoK(int intArr[],int arrMax, int K)
{
    int moreCount;
    for (int index = 0; index < arrMax; index++)
    {
        moreCount = 0;
        for (int restIndex = 0; restIndex < arrMax; restIndex++)
        {
            if (index == restIndex) continue;
            if (intArr[index] > intArr[restIndex]) moreCount++;
        }

        if (moreCount == K - 1)
        {
            return intArr[index];
        }

    }

    return -1;
}

//主函数里
int _tmain(int argc, _TCHAR* argv[])
{
    int iArr[] = { 1, 6, 9, 0, 4, 5 };
    int Max = sizeof(iArr) / sizeof(iArr[0]);
    int result = getNoK(iArr, Max, 3);
    cout << result << endl;
    system("pause");
}


输出:4
也就是第3名,是4

vs2013+win7(32位)测试通过
︿ 0
说明:以上算法没有考虑重复元素
效率最坏是O(N^2)

LZ可以考虑另一种思路,时间有限,我就不研究了
你可以将所有元素分组(按顺序分),每组K+1个元素,零头放到最后一个组,做特别处理
建立struct数组,将每个组的情况放到一个数组元素中
struct group
{
    int 组内元素数;
    int 组内排名;
}
……
︿ 0
网上搜索一个排序算法(最基础的就是冒泡排序算法)
如果从大到小排序,那么第k大的数就是 a[k-1] //a代表输入的数组
如果从小到大排序,那么第k大的数就是 a[n-k] //n代表数组个数