算法导论:快速找出无序数组中第k小的数

时间:2021-12-06 10:48:23

题目描述:

给定一个无序整数数组,返回这个数组中第k小的数。

解析:

最平常的思路是将数组排序,最快的排序是快排,然后返回已排序数组的第k个数,算法时间复杂度为O(nlogn),空间复杂度为O(1)。使用快排的思想,但是每次只对patition之后的数组的一半递归,这样可以将时间复杂度将为O(n)。

 在《算法导论》有详细叙述 这里主要用C++实现,实现思路就是先选取当前数组的第一个数作为“主轴”,将后面所有数字分成两部分,前面一部分小于“主轴”,后面一部分大于“主轴”,然后计算前面一部分数字的有多少,如果大于K则递归--在前面一部分找第K个数,如果小于K则在后面一部分呢找,此时K要更新一下 K需要减去第一部分数字数目,递归查找。递归的细节自己掌握以下就行,思路基本就是这样。

代码实现:

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

/*
题目描述:
给定一个无序整数数组,返回这个数组中第k小的数。
实现思路: 就是先选取当前数组的第一个数作为“主轴”,将后面所有数字分成两部分,前面一部分小于“主轴”,后面一部分大于“主轴”,然后计算前面一部分数字的有多少,如果大于K则递归--在前面一部分找第K个数,如果小于K则在后面一部分呢找,此时K要更新一下 K需要减去第一部分数字数目,递归查找
 */

void swap(int *p, int *q)
{
    int t;
    t = *p;
    *p = *q;
    *q = t;
}

int findNumberK(vector<int> &vec, int k, int s, int e)
// 快速排序(折半缩小递归区间的方法)查找 The K
{
    int roll = vec[s], be = 0, j = s;

    for(int i = s+1 ; i<= e ; i++)
    {
        if(vec[i] < roll)
        {
            j++;
            swap(&vec[i], &vec[j]);
            be++;
        }
    }

    swap(&vec[s], &vec[j]);

    if(be == k - 1 )
        return roll;
    else if (be < k - 1)
    {
        return findNumberK(vec, k - be - 1, j + 1, e);
    }
    else
        return findNumberK(vec, k, s, j - 1);
}

int main()
{

    vector<int> a;
    int temp, k;

    cout << "input data:" << endl;
    cin >> temp;

    while(temp != 0)
    {
        a.push_back(temp);
        cin >> temp;
    }

    cout << "input K: " << endl;
    cin >> k;

    int number = findNumberK(a , k, 0 ,a.size() - 1);
    cout << "Test Result: "  << number<< endl;
    /*
    The next use sort 模板快排进行结果验证
     */

    sort(a.begin(), a.end(), less<int>());
    cout << "real Result: "  << a[k-1] << endl;
    return 0;
}

执行结果:

算法导论:快速找出无序数组中第k小的数