C++语言编程 急急!!! 用分治策略

设计一个平均时间为O(n)的算法,在n(1<=n<=1000)个无序的整数中找出第k小的数。

提示:函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x(如a[left])对a[left]~a[right]进行划分,划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int right,int k)函数,通过调用partition函数获得划分点,判断划分点是否第k小,若不是,递归调用find函数继续在左段或右段查找。

输入格式:
输入有两行:

第一行是n和k,0<k<=n<=10000

第二行是n个整数

输出格式:
输出第k小的数

输入样例:
在这里给出一组输入。例如:

10 4
2 8 9 0 1 3 6 7 8 2
输出样例:
在这里给出相应的输出。例如:

2

2个回答

 #include <stdio.h>

void swap(int a[], int i, int j)
{
    // 交换数组a中元素i与元素j的值
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

int partition(int a[], int lo, int hi)
{
    int i = lo-1, pivot = a[lo];
    swap(a, lo, hi);
    while(lo<hi)
    {
        // 循环开始的时候i指向的是小于pivot的最后的一个位置
        if(a[lo] < pivot)
        {
            i ++;
            swap(a, i, lo);
        }
        lo ++;
    }
    i ++;
    swap(a, i, hi);
    return i;
}

int find(int a[], int left, int right, int k)
{
    int index;
    index = partition(a, left, right);
    if(index == k)
        return a[index];
    else if(index < k)
        return find(a, index+1, right, k);
    else
        return find(a, left, right-1, k);
}

int main()
{
    int a[10000];
    int n, k, i;
    scanf("%d", &n);
    scanf("%d", &k);
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);
    printf("%d\n", find(a, 0, n-1, k-1));
}

#include
using namespace std;
int a[30005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i {
int x;
cin>>x;
a[x]=1;
}
for(int i=1;i<=30000;i++)
{
if(a[i]==1)k--;
if(k==0){cout<<i;return 0;}
}
cout<<"NO RESULT";
return 0;
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问