给出一个算法的伪代码，给定集合｛0，1，

Question

问题陈述：

给出一个算法的伪代码，给定集合{0，1，…，k−1}中n个整数的列表，对其输入进行预处理，以提取和存储信息，从而可以回答任何询问n个整数中有多少落在[a.b]范围内（a和b是查询的输入参数）O（1）时间。解释你的算法是如何工作的。在最坏的情况下，预处理时间应该是O（n+k）。提供一个论点，表明预处理算法满足这个界限。

我的尝试：

Counting Sort Pseudo Code
function countingSort(array, min, max)
  count: array of (max – min + 1) elements //max is highest number, min is lowest 
  initialize count with 0 //set count = 0
  for each number in array do
    count[number – min] := count[number-min] + 1 //element i – min element = pos. 
                                                 //pos + 1
  done
  z:= 0
  for i from min to max do
    while(count[ i – min] >0) do
      array[z] := i
      z := z + 1
      count[i – min] := count [i – min] – 1
    done
   done
Find Pseudo Code
find(a, b)
  ??

时间复杂性分析：我们发现计数排序的总时间复杂度需要O（k）时间来初始化数组，需要O（n）时间来读入数字并增加适当的计数元素。另一个O（k）用于创建数组z，另一个0（n）用于扫描并读取O（n+k）的总运行时间的数字列表。

问题：我遇到的唯一问题是，我不知道如何向用户报告在O（1）时间内位于他们选择的范围[a.b]之间的整数的数量。。我能想到的检索该信息的唯一方法是循环遍历我的排序整数数组，每次找到一个数字时都有一个计数器递增，这样一些元素就>=a&amp；某些元素是<=b.我应该在搜索中包括他们输入的实际数字吗？还是应该只计算他们之间的数字？在数组中循环并有一个计数器来计数[a.b]之间的数字的问题是，这需要一个for循环，并且是O（n）。如有任何帮助，将不胜感激

Answer 1

答案很琐碎，只是没有想过。在我使用计数排序后，它会返回我的列表，所以我所要做的就是从用户要求的范围中取差。例如

find(a,b)
  numberofIntegersBetweenAandB = count[b] - count[a] 

Answer 2

使用C++示例。由于这里的目标是psuedo代码，所以没有错误检查。

int * GenerateSums(int a[], size_t n, int min, int max)
{
    size_t k = max + 2 - min;
    int *sums = new int[k];
    for(size_t i = 0; i < k; i++)   // clear sums
        sums[i] = 0;
    for(size_t i = 0; i < n; i++)   // set number of instances
        sums[1+a[i]-min]++;
    for(size_t i = 1; i < k; i++)   // convert to cumulative sums
        sums[i] += sums[i-1];
    return sums;
}
int CountInRange(int sums[], int a, int b)
{
    return sums[b+1] - sums[a];
}
int main()
{
    int a[] = {4,0,3,4,2,4,1,4,3,4,3,2,4,2,3,1};
    int *sums = GenerateSums(a, sizeof(a)/sizeof(a[0]), 0, 4);
    int cnt;
    cnt = CountInRange(sums, 0, 0);  // returns  1
    cnt = CountInRange(sums, 3, 4);  // returns 10
    cnt = CountInRange(sums, 0, 4);  // returns 16
    delete[] sums;
    return 0;
}