Рубрики

Подсчитайте меньшие элементы на правой стороне

Напишите функцию для подсчета количества меньших элементов справа от каждого элемента в массиве. Учитывая несортированный массив arr [] различных целых чисел, создайте другой массив countSmaller [] так, чтобы countSmaller [i] содержал количество меньших элементов с правой стороны каждого элемента arr [i] в массиве.

Примеры:

Input:   arr[] =  {12, 1, 2, 3, 0, 11, 4}
Output:  countSmaller[]  =  {6, 1, 1, 1, 0, 1, 0} 

(Corner Cases)
Input:   arr[] =  {5, 4, 3, 2, 1}
Output:  countSmaller[]  =  {4, 3, 2, 1, 0} 

Input:   arr[] =  {1, 2, 3, 4, 5}
Output:  countSmaller[]  =  {0, 0, 0, 0, 0}

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

Способ 1 (простой)
Используйте две петли. Внешний цикл выбирает все элементы слева направо. Внутренний цикл перебирает все элементы с правой стороны выбранного элемента и обновляет countSmaller [].

С

void constructLowerArray (int *arr[], int *countSmaller, int n)

{

  int i, j;

  

  // инициализируем все значения в массиве countSmaller как 0

  for  (i = 0; i < n; i++)

     countSmaller[i] = 0;

  

  for (i = 0; i < n; i++)

  {

    for (j = i+1; j < n; j++)

    {

       if (arr[j] < arr[i])

         countSmaller[i]++;

    }

  }

}

  
/ * Служебная функция, которая печатает массив в строке * /

void printArray(int arr[], int size)

{

  int i;

  for (i=0; i < size; i++)

    printf("%d ", arr[i]);

  

  printf("\n");

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

  int arr[] = {12, 10, 5, 4, 2, 20, 6, 1, 0, 2};

  int n = sizeof(arr)/sizeof(arr[0]);

  int *low = (int *)malloc(sizeof(int)*n);

  constructLowerArray(arr, low, n);

  printArray(low, n);

  return 0;

}

Джава

class CountSmaller 

{

    void constructLowerArray(int arr[], int countSmaller[], int n) 

    {

        int i, j;

  

        // инициализируем все значения в массиве countSmaller как 0

        for (i = 0; i < n; i++)

            countSmaller[i] = 0;

  

        for (i = 0; i < n; i++) 

        {

            for (j = i + 1; j < n; j++) 

            {

                if (arr[j] < arr[i])

                    countSmaller[i]++;

            }

        }

    }

  

    / * Служебная функция, которая печатает массив в строке * /

    void printArray(int arr[], int size) 

    {

        int i;

        for (i = 0; i < size; i++)

            System.out.print(arr[i] + " ");

  

        System.out.println("");

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        CountSmaller small = new CountSmaller();

        int arr[] = {12, 10, 5, 4, 2, 20, 6, 1, 0, 2};

        int n = arr.length;

        int low[] = new int[n];

        small.constructLowerArray(arr, low, n);

        small.printArray(low, n);

    }

}

C #

using System;

  

class GFG {

      

    static void constructLowerArray(int []arr,

                    int []countSmaller, int n) 

    {

        int i, j;

  

        // инициализируем все счета в

        // массив countSmaller как 0

        for (i = 0; i < n; i++)

            countSmaller[i] = 0;

  

        for (i = 0; i < n; i++) 

        {

            for (j = i + 1; j < n; j++) 

            {

                if (arr[j] < arr[i])

                    countSmaller[i]++;

            }

        }

    }

      

    / * Утилита, которая печатает

    массив в строке * /

    static void printArray(int []arr, int size) 

    {

        int i;

        for (i = 0; i < size; i++)

            Console.Write(arr[i] + " ");

  

        Console.WriteLine("");

    }

      

    // Функция драйвера

    public static void Main()

    {

        int []arr = new int[]{12, 10, 5, 4, 

                            2, 20, 6, 1, 0, 2};

        int n = arr.Length;

        int []low = new int[n];

          

        constructLowerArray(arr, low, n);

        printArray(low, n);

    }

}

  
// Этот код предоставлен Sam007


Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (1)

Способ 2 (использовать самобалансировку BST)
Самобалансирующееся дерево бинарного поиска (AVL, Red Black, … и т. Д.) Может использоваться для получения решения за O (nLogn) сложность времени. Мы можем расширить эти деревья, чтобы каждый узел N содержал размер поддерева с корнем N. Мы использовали дерево AVL в следующей реализации.

Мы пересекаем массив справа налево и вставляем все элементы один за другим в дерево AVL. Вставляя новый ключ в дерево AVL, мы сначала сравниваем ключ с root. Если ключ больше, чем корень, то он больше, чем все узлы в левом поддереве корня. Таким образом, мы добавляем размер левого поддерева к количеству меньшего элемента для вставляемого ключа. Мы рекурсивно используем один и тот же подход для всех узлов вниз по корню.

Ниже приводится реализация C.

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

  
// Узел дерева AVL

struct node

{

    int key;

    struct node *left;

    struct node *right;

    int height;

    int size; // размер дерева с этим узлом

};

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b);

  
// Вспомогательная функция для получения высоты дерева с корнем N

int height(struct node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}

  
// Функция полезности для размера дерева с корнем с N

int size(struct node *N)

{

    if (N == NULL)

        return 0;

    return N->size;

}

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b)

{

    return (a > b)? a : b;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и

    NULL левый и правый указатели. * /

struct node* newNode(int key)

{

    struct node* node = (struct node*)

                        malloc(sizeof(struct node));

    node->key   = key;

    node->left   = NULL;

    node->right  = NULL;

    node->height = 1;  // новый узел изначально добавляется в лист

    node->size = 1;

    return(node);

}

  
// Полезная функция для правого поворота поддерева с корнем у

struct node *rightRotate(struct node *y)

{

    struct node *x = y->left;

    struct node *T2 = x->right;

  

    // Выполнить вращение

    x->right = y;

    y->left = T2;

  

    // Обновление высоты

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;

  

    // Обновить размеры

    y->size = size(y->left) + size(y->right) + 1;

    x->size = size(x->left) + size(x->right) + 1;

  

    // Возвращаем новый корень

    return x;

}

  
// Вспомогательная функция левого поворота поддерева с корнем x

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    struct node *T2 = y->left;

  

    // Выполнить вращение

    y->left = x;

    x->right = T2;

  

    // Обновление высоты

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;

  

    // Обновить размеры

    x->size = size(x->left) + size(x->right) + 1;

    y->size = size(y->left) + size(y->right) + 1;

  

    // Возвращаем новый корень

    return y;

}

  
// Получить коэффициент баланса узла N

int getBalance(struct node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

  
// Вставляет новый ключ в дерево, загнившее с узла. Также обновления * рассчитывают
// содержать количество меньших элементов для нового ключа

struct node* insert(struct node* node, int key, int *count)

{

    / * 1. Выполнить обычное вращение BST * /

    if (node == NULL)

        return(newNode(key));

  

    if (key < node->key)

        node->left  = insert(node->left, key, count);

    else

    {

        node->right = insert(node->right, key, count);

  

        // ОБНОВЛЕНИЕ СЧЕТА МАЛЕНЬКИХ ЭЛЕМЕНТОВ ДЛЯ КЛЮЧА

        *count = *count + size(node->left) + 1;

    }

  

  

    / * 2. Обновление высоты и размера этого узла-предка * /

    node->height = max(height(node->left), height(node->right)) + 1;

    node->size   = size(node->left) + size(node->right) + 1;

  

    / * 3. Получить коэффициент баланса этого узла-предка, чтобы проверить,

       этот узел стал неуравновешенным * /

    int balance = getBalance(node);

  

    // Если этот узел становится несбалансированным, то есть 4 случая

  

    // Левый левый регистр

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

  

    // правый правый случай

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

  

    // левый правый регистр

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }

  

    // Правый левый регистр

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Следующая функция обновляет массив countSmaller, чтобы он содержал счетчик
// меньшие элементы на правой стороне.

void constructLowerArray (int arr[], int countSmaller[], int n)

{

  int i, j;

  struct node *root = NULL;

  

  // инициализируем все значения в массиве countSmaller как 0

  for  (i = 0; i < n; i++)

     countSmaller[i] = 0;

  

  // Начиная с самого правого элемента, вставляем все элементы один за другим в

  // AVL дерево и получаем количество меньших элементов

  for (i = n-1; i >= 0; i--)

  {

     root = insert(root, arr[i], &countSmaller[i]);

  }

}

  
/ * Служебная функция, которая печатает массив в строке * /

void printArray(int arr[], int size)

{

  int i;

  printf("\n");

  for (i=0; i < size; i++)

    printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

  int arr[] = {10, 6, 15, 20, 30, 5, 7};

  int n = sizeof(arr)/sizeof(arr[0]);

  

  int *low = (int *)malloc(sizeof(int)*n);

  

  constructLowerArray(arr, low, n);

  

  printf("Following is the constructed smaller count array");

  printArray(low, n);

  return 0;

}

Выход:

Following is the constructed smaller count array
3 1 2 2 2 0 0

Сложность времени: O (nLogn)
Вспомогательное пространство: O (n)

Подсчитайте меньшие элементы на правой стороне, используя Set в C ++ STL

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитайте меньшие элементы на правой стороне

0.00 (0%) 0 votes