c - 如何查找大于/小于数组中元素的元素数？

Question

我想找到最快的方法来查找小于/大于数组中每个元素的元素数。

例如:数组是[5, 6, 8, 2, 4]。考虑第一个元素，没有比它小的元素是 2。

我能做的最好的事情是将每个元素与数组的其余元素进行比较，但是对于条目数约为 10^5 的大型数组来说，这需要很长时间。

我的代码:

for(i=0;i<n;i++)
{
    count=0;
    for(j=0;j<n;j++)
    {
        if( i!=j && (ar[i]>ar[j]) )
        {
            count++;
        }
    }
    printf("%lld ",count);
}

编辑:我想显示小于每个数组元素的元素数。对于上面的例子，我希望答案是:2 3 4 0 1 并且数组可以包含重复的值。

Answer 1

以下代码片段将帮助您进行查询。
它是使用二进制搜索 实现的，因此可以实现 log(n) 时间复杂度，
其中 n 是数组中元素的数量。

请注意，您需要先对数组进行排序。
因此总体时间复杂度为n*log(n)。

#include<bits/stdc++.h>
using namespace std;

int binarySearchLargerElenents(int arr[], int val){
    int l = 0;
    int size = sizeof(arr)/sizeof(arr[0]);
    int r = size-1;
    int resultantIndex = size;
    while(l<=r){
        int mid = l + (r-l) / 2;
        if(arr[mid] <= val){
            l = mid +1;
        }
        else{
            r = mid -1;
            resultantIndex = mid;
        }
    }
    return (size-resultantIndex);
}

int binarySearchSmallerElements(int arr[], int val){
    int l = 0;
    int size = sizeof(arr)/sizeof(arr[0]);
    int r = size-1;
    int resultantIndex = size;
    // strictly less than val.
    // while(l<=r){
    //   int mid = l + (r - l) / 2;
    //   if(arr[mid] < val){
    //     l = mid + 1;
    //
    //   }
    //   else{
    //     r = mid - 1;
    //     resultantIndex = mid;
    //   }
    // }

    // less that or equal to val
    while(l<=r){
        int mid = l + (r-l) / 2;
        if(arr[mid] <= val){
            l = mid +1;
        }
        else{
            r = mid-1;
            resultantIndex = mid;
        }
    }
    return resultantIndex;
}
int main(){
    int arr[] = {1, 2, 3, 4, 5, 5, 7};
    int x;
    cout<<"Input x: ";
    cin>>x;
    int countOfSmallerElements = binarySearchSmallerElements(arr, x);
    int countOfLargerElements = binarySearchLargerElenents(arr, x);

    cout<<" smaller than "<<x <<" : "<< countOfSmallerElements<<endl;
    cout<<" larger than "<<x <<" : "<< countOfLargerElements<<endl;
}