比較數字和陣列

我正在嘗試將一個數字與包含某些未知值的陣列進行比較，并且我想獲得小于比較數字的整數數量。

例如：

該陣列將是： -2 5 2 5 7 9 10

比較數為： 8

回答： 5

#include <stdio.h>
#include <stdlib.h>

long long data[200000] = { 0 };

int cmpfunc(const void *a, const void *b) {
    return (*(long long*)b - *(long long*)a);
}

int main() {
    int numbers, i, j, z, counter, testcases;
    long long check;
    scanf("%d", &numbers);
    for (i = 0; i < numbers; i  )
        scanf("%lld", &data[i]);

    qsort(data, numbers, sizeof(long long), cmpfunc);

    scanf("%d", &testcases);
    for (j = 0; j < testcases; j  ) {
        scanf("%lld", &check);
        counter = numbers;
        
        for (z = 0; z < numbers; z  ) {
            if (check >= data[z])
                break;
            counter--;
        }
        printf("%d\n", counter);
    }
}

我的程式仍然比要求允許的運行速度慢，有什么辦法可以讓它更快？

uj5u.com熱心網友回復：

您的方法存在一些問題：

• 如果 2 個數字的差超過 type 的范圍，則比較函式將無法正常作業int，即使使用int值也很容易實作，例如：比較INT_MAX和INT_MIN。你應該改用這個：

    int cmpfunc(const void *aa, const void *bb) {
        const long long *a = aa;
        const long long *b = bb;
        return (*a > *b) - (*a < *b);
    }
  

• 對值進行排序對于您的目標而言并不總是必要的：只有在查找次數大于log2(N)對陣列進行排序所花費的時間與N.log(N)成正比時才有用。

• 此外，您應該利用排序，使用二進制搜索來定位數字潛在位置并直接從該位置確定計數。當前使用線性搜索的方法與排序和未排序陣列的作業方式相同。

• 除非它是分配的一部分，否則 200000 可能不足以用于所有測驗用例。分配陣列似乎是一種更好的方法。

這是一個修改后的版本：

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *aa, const void *bb) {
    const long long *a = aa;
    const long long *b = bb;
    return (*a > *b) - (*a < *b);
}

int main() {
    int numbers, i, j, z, counter, testcases;
    long long *data;
    long long check;

    if (scanf("%d", &numbers) != 1)
        return 1;
    data = calloc(sizeof(*data), numbers);
    if (!data)
        return 1;
    for (i = 0; i < numbers; i  ) {
        if (scanf("%lld", &data[i]) != 1)
            return 1;
    }
    if (scanf("%d", &testcases) != 1)
        return 1;

    if (testcases < 63 && (1ULL << testcases) < numbers) {
        for (j = 0; j < testcases; j  ) {
            if (scanf("%lld", &check) != 1)
                return 1;
            counter = 0;
            
            for (z = 0; z < numbers; z  ) {
                counter  = (check < data[z]);
            }
            printf("%d\n", counter);
        }
    } else {
        qsort(data, numbers, sizeof(*data), cmpfunc);
        for (j = 0; j < testcases; j  ) {
            if (scanf("%lld", &check) != 1)
                return 1;

            size_t a = 0, b = numbers;
            while (a < b) {
                size_t m = a   (b - a) / 2;
                if (data[m] < check)
                    a = m   1;
                else
                    b = m;
            }
            counter = b;
            printf("%d\n", counter);
        }
    }
    free(data);
    return 0;
}

uj5u.com熱心網友回復：

二進制與線性

而不是線性搜索

    for (z = 0; z < numbers; z  ) {
        if (check >= data[z])
            break;
        counter--;
    }

使用二進制

    found = false;
    int lo = 0;
    int hi = numbers - 1;
    while (lo <= hi) {
      int mid = (hi-lo)/2   lo;
      if (data[mid] < check) lo = mid   1;
      else if (data[mid] > check) hi = mid - 1;
      else {
        found = true;
        // found it!
        // Now look for first index less than check with TBD code.
      }
    }  
         
    // Value of lo, hi  can be use to determine the count. 

避免溢位

*(long long*)b - *(long long*)a 可能會溢位。

int cmpfunc(const void *a, const void *b) {
  // return (*(long long*)b - *(long long*)a);
  return (*(long long*)b > *(long long*)a) - (*(long long*)b < *(long long*)a);
}

標籤：C

上一篇：C中的malloc和陣列

下一篇：為什么“免費”說我的指標無效？