时间戳

首页 > 解决方案 > 在非常大的数组中计算较小或相等元素的更快方法？

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

问题描述

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

重要细节：

例子 ：

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

阵列：1002 19 3 8 22 123 14 5234 123 657 41 829 34 2314 15

查询 : 100 1000 78 3 1

输出：8 12 8 1 0

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

#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;
}

标签： arraysalgorithmsearch

解决方案

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

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

如果您不能使用标准库中的排序例程，只需更改您的实现 - 在随机索引处获取枢轴或使用“三的中位数”方法

PS 还可以考虑用 Hoare 的方法替换使用过的 Lomuto 的分区方法（它不是那么简单但更快）

推荐阅读