0

给定一个整数数组，第 90 个百分位是第一个超过 90% 数组的数字。如果您想要更具体的定义，请查看http://studentnet.cs.manchester.ac.uk/ugt/COMP26120/lab/ex6def.html

我编写了一个快速选择程序，可以在正常情况下成功运行。那是部分排序，仅对第 90 个百分位数包含的一侧进行排序。

但是对于特殊情况，如果所有整数都相同，并且没有第 90 个百分位数，它仍然会找到第 90 个数字，但不会返回 -1。

请确保修正后的程序是O(n)。

如果我在主函数中使用循环重复调用快速选择函数来比较第 (k-1) 个数字和第 k 个数字，运行时间将 (nk)*n=O(n^2) （快速选择在 O （n）我用谷歌搜索）。在选择时找到有效的第 90 个数字是否更简单？

Here are my codes:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>  
#define N 23

void swap ( int *a, int *b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
int partition(int *a, int high){ //high is the last index of this array
    int i,j,pivotValue;
    i = -1;
    j = 0;
    pivotValue = a[high]; 
    for ( j=0; j<high; j++){
        if ( a[j]> pivotValue){
            continue;
        }
        i++;
        swap(&a[i], &a[j]);
    }
    return i+1;
}
int quickSelect(int a[],int n, int k) { //n is the size of the array
    int pivotIndex;
    pivotIndex = partition(a, n-1);
    if ( pivotIndex >= k ){//left.size = pivotIndex
        printf("left\n");

        return quickSelect(a, pivotIndex, k);
    }
    else if ( (pivotIndex+1)==k ){
        printf("pivot\n");
        return a[n-1];
    }
    else{
        printf("right\n");
        return quickSelect(&a[pivotIndex], n-(pivotIndex+1), k-(pivotIndex+1));
    }
}


int main()
{
int a[] = {1612,1894,3018,4212,6046,12894,13379,14408,14615,16394,17982,23004,27588,31393,33195,39526,54326,54566,60000,60000,60000,60000,703908};

    int find,k;

    k = floor(N*0.9)+1;
    printf("k=%d\n",k);

    find = quickSelect(a, N, k);

    printf("the 90th number=%d\n",find);

    return 0;
}
4

0 回答 0