Algorithm: find the number of numbers in a given range

Question

for an array of unsorted numbers, where there may be duplicates, pre-process the array to find the number of numbers in a given range, time O (1).

For example, 7,2,3,2,4,1,4,6 . The number of numbers >= 2 and <= 5 is 5 . (2,2,3,4,4) .

Answer 1

Sort an array. For each element in the sorted array, insert this element in the hash table with the element value as the key and its position in the array as the associated value. Any values ​​that are missing, you will also need to insert.

To find the number of elements in a range, find the position of the value at each end of the range in the hash table and subtract the bottom from the top to find the size of the range.

Answer 2

This sounds suspicious, like one of those clever interviews that some interviewers ask, which are usually related to tips on the way to how you think.

Regardless ... one of the possible ways to implement this is to make a list of counters of numbers equal to or less than the index of the list.

For example, from the list above, generate a list: 0, 1, 3, 4, 6, 6, 7, 8. Then you can count numbers from 2 to 5 by subtracting list [1] from list [5].

Answer 3

Since we need to access O (1), the required data structure will be memory intensive.
With a hash table, in the worst case, access will take O (n)

My decision:
Building a 2D matrix.
array = {2,3,2,4,1,4,6} The range of numbers is from 0 to 6, so n = 7
So we have to create the nxn matrix.
array [i] [i] represents the total count of the element = i
therefore array [4] [4] = 2 (since 4 appears in the array 2 times)
array [5] [5] = 0
array [5] [2] = the number of numbers, both> = 2 and <= 5 = 5

 //preprocessing stage 1: Would populate a[i][i] with total count of element = i a[n][n]={0}; for(i=0;i<=n;i++){ a[i][i]++; } //stage 2 for(i=1;i<=n;i++) for(j=0;j<i;j++) a[i][j] = a[i-1][j] + a[i][i]; //we are just adding count of element=i to each value in i-1th row and we get ith row. 

Now (5.2) will query for [5] [2] and give an answer in O (1)

Answer 4

 int main() { int arr[8]={7,2,3,2,4,1,4,6}; int count[9]; int total=0; memset(count,0, sizeof(count)); for(int i=0;i<8;i++) count[arr[i]]++; for(int k=0;k<9;k++) { if(k>=2 && k<=5 && count[k]>0 ) { total= total+count[k] ; } } printf("%d:",total); return 0; }