C语言高效统计大动态数组区间内元素数量的优化方案咨询

问题背景 #

我有一个包含200000+元素的动态分配数组，元素随机排列且存在重复，需要统计落在指定区间内的元素数量。

• 数组示例：

  {1,2,3,1484984,48941651,489416,1816,168189161,6484,8169181,9681916,121,231,684979,795641,231484891,...}
  

• 指定区间示例：<2;150000>
• 工作程序示例：

  { 1, 7, 22, 4, 7, 5, 11, 9, 1 }
  <4;7>
  -> 4
  

当前低效实现 #

我现在用双层for循环实现，效率极低：

for( int j = 0; j <= numberOfRepeats; j++){
        for( int i = 0; i < arraySize; i++){
            if(currentNumber == array[i]){
            counter++;
           }
        }
        currentNumber++;
    }
    printf(" -> %d\n", counter);       
}

高效实现方案 #

方案1：排序+二分查找 #

排序确实能大幅提升效率，而且对于20万级别的数据，排序的开销完全可以接受。

• 步骤：
  1. 先对数组进行排序，时间复杂度为O(n log n)，20万元素的排序在现代CPU上只需要几毫秒。
  2. 使用二分查找找到区间左边界的第一个位置，再找到区间右边界的最后一个位置，两者的下标差就是区间内元素的总数，这一步时间复杂度为O(log n)。
• 示例代码（C语言）：

  #include <stdio.h>
  #include <stdlib.h>
  
  // 比较函数，用于qsort
  int compare(const void *a, const void *b) {
      return (*(int*)a - *(int*)b);
  }
  
  int countInRange(int *array, int size, int lower, int upper) {
      // 排序数组
      qsort(array, size, sizeof(int), compare);
      
      // 找第一个 >= lower 的元素下标
      int *left = (int*)bsearch(&lower, array, size, sizeof(int), compare);
      if (!left) {
          // 所有元素都小于lower，返回0
          return 0;
      }
      int left_idx = left - array;
      
      // 找第一个 > upper 的元素下标
      int temp = upper + 1;
      int *right = (int*)bsearch(&temp, array, size, sizeof(int), compare);
      int right_idx;
      if (right) {
          right_idx = right - array;
      } else {
          // 所有元素都 <= upper，右边界是数组末尾
          right_idx = size;
      }
      
      return right_idx - left_idx;
  }
  
  int main() {
      int array[] = {1,7,22,4,7,5,11,9,1};
      int size = sizeof(array)/sizeof(array[0]);
      int lower = 4, upper =7;
      printf(" -> %d\n", countInRange(array, size, lower, upper));
      return 0;
  }
  

方案2：哈希表统计频率 #

如果需要多次查询不同区间，用哈希表预统计每个元素的出现次数会更高效：

• 步骤：
  1. 遍历数组一次，用哈希表（或自定义计数桶，若元素数值范围可控）统计每个数字的出现次数，时间复杂度O(n)。
  2. 遍历区间内的所有数字，累加它们的出现次数，时间复杂度取决于区间内不同数字的数量，实际查询速度极快。
• 注意：如果元素数值范围极大（如超过1e9），哈希表是更优选择；若数值范围不大，直接用数组作为计数桶效率更高。

关于排序的开销问题 #

对于20万级别的整数数组，用标准库的qsort排序完全不会“太慢”——现代CPU处理这种规模的排序仅需几毫秒，相比你当前双层循环O(n^2)的时间复杂度（20万元素会产生4e10次操作，完全无法接受），排序的开销可以忽略不计，后续的二分查找更是瞬间完成。

内容的提问来源于stack exchange，提问作者Grolldash