arrays - 在一个非常大的数组中计算较小或相等元素的更快方法？

Question

我需要降低代码的时间复杂度，到目前为止，我尝试对其进行预排序并使用二进制搜索来查找所需元素的索引，并使用索引来查找键号之前的元素数量，但我不能' t pass因为我的代码很慢。有没有其他方法可以让这段代码更快？

重要细节:

• 我需要使用一个大数组和多个查询(数组保持不变)来运行此代码，两者最多 100k。
• 每个元素的值最多为10亿。
• 这道题的时限是0.1s

示例:

假设我有一个包含 15 个元素的数组，并且我有 5 个查询要做。

数组:1002 19 3 8 22 123 14 5234 123 657 41829 34 2314 15

查询:100 1000 78 3 1

输出:8 12 8 1 0

我尝试对其进行预排序并使用二进制搜索，但我仍然无法通过 0,1 秒的时间限制。

#include<stdio.h>

void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}

int partition(int a[],int p,int r){
    int temp, i,x;
    x=a[r];
    i=p-1;
    for(int j=p;j<=r;j++){
        if(a[j]<x){
            i++;
            swap(&a[i],&a[j]);
        }
    }
    i++;
    swap(&a[i],&a[r]);;
    return i;
}

void qsort(int a[],int p,int r){
    int q;
    if(p<r){
        q=partition(a,p,r);
        qsort(a,p,q-1);
        qsort(a,q+1,r);
    }
}

int binarySearch(int arr[], int n, int key){ 
    int left = 0, right = n; 
    int mid; 
    while (left < right){ 
        mid = left + (right-left)/2; 
        if (arr[mid] == key){ 
            while (arr[mid+1] == key && mid+1<n) 
                 mid++; 
            break; 
        }else if (arr[mid] > key) 
            right = mid; 
        else
            left = mid + 1; 
    } 
    while (arr[mid] > key) 
        mid--; 
    return mid + 1; 
} 

int main(){
    int a, b;
    scanf("%d %d",&a, &b);
    int data[a],d;
    for(int i=0;i<a;i++){
        scanf("%d", &data[i]);
    }   
    qsort(c, 0, a-1);
    for(int i=0;i<b;i++){
        scanf("%d", &d);
        printf("%d\n", binarySearch(c, a, d));
    }
    return 0;
}

Answer 1

总的来说，您的方法是正确的，应该提供平均时间 NlogN + MlogN，其中 N 是数组大小，M 是查询数。

但是 qsort 的实现还不够好 - 它总是选择正确的元素作为主元，并且对于某些数组(已经排序的数组或包含重复元素)给出二次排序时间!

如果您不能使用标准库中的排序例程，只需更改您的实现 - 在随机索引处获取主元或使用“median of three”方法

附言还可以考虑用 Hoare 的方法替换使用过的 Lomuto 的分区方法(它不是那么简单但更快)