Алгоритм: найти количество чисел в заданном диапазоне

Question

с учетом массива несортированных чисел, в котором могут быть дубликаты, предварительно обработайте массив, чтобы найти число чисел в данном диапазоне, время O (1).

Например, 7,2,3,2,4,1,4,6.Количество чисел >= 2 и <= 5 равно 5.(2,2,3,4,4).

Answer 1

Сортировка массива.Для каждого элемента в отсортированном массиве вставьте этот элемент в хеш-таблицу, указав значение элемента в качестве ключа и его положение в массиве в качестве связанного значения.Все пропущенные значения вам также нужно будет вставить.

Чтобы найти количество элементов в диапазоне, найдите положение значения на каждом конце диапазона в хэш-таблице и вычтите нижнее из верхнего, чтобы найти размер диапазона.

Answer 2

Это звучит подозрительно, как один из тех умных вопросов для интервью, которые некоторые интервьюеры любят задавать, что обычно связано с подсказками, чтобы узнать, как вы думаете.

Независимо ... один из возможных способов реализации этогосостоит в том, чтобы составить список из чисел, равных или меньших индекса списка.

Например, из приведенного выше списка создайте список: 0, 1, 3, 4, 6, 6, 7, 8. Затем вы можете посчитать числа от 2 до 5, вычитая список [1] ​​из списка [5].

Answer 3

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;
}

Answer 4

Поскольку нам необходим доступ в O (1), необходимая структура данных будет требовать большого объема памяти.
При использовании таблицы хэширования в худшем случае для доступа потребуется O (n)

Мое решение:
Построить 2D матрицу.
array = {2,3,2,4,1,4,6} Диапазон чисел = от 0 до 6, поэтому n = 7
Итак, мы должны создать матрицу nxn.
array [i] [i] представляет общее количество элементов = i
, поэтому array [4] [4] = 2 (так как 4 появляется в массиве 2 раза)
array [5] [5]= 0
array [5] [2] = количество чисел>> = 2 и <= 5 = 5 </p>

//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.

Теперь (5,2) будет запрашивать [5] [2] и даст ответ в O (1)