C++ 中查找右侧较小元素的数量

2024年8月28日 | 阅读 7 分钟

在本文中，我们将讨论如何使用 C++ 计算右侧较小元素，并提供几个示例。

下面是 N 维无序数组 arr[]，它由唯一整数组成。我们的目标是创建一个名为 count 的第二个数组，其中 count 将更小。右侧小于 arr[i] 的元素数量将由 smaller[i] 变量表示。

示例

示例 1：

输入

N = 5, arr[] = {7, 4, 6, 2, 1}

输出

{3, 2, 2, 1, 0}

说明

对于 arr[0]，右侧有三个元素小于 7，它们是 {4, 6, 2}。
对于 arr[1]，右侧有两个元素小于 4，它们是 {2, 1}。
对于 arr[2]，右侧有两个元素小于 6，它们是 {2, 1}。
对于 arr[3]，右侧有一个元素小于 2，它是 {1}。
对于 arr[4]，右侧没有更小的元素。

示例 2

输入

N=5, arr[] = {7, 1, 5, 2, 10}

输出

{3, 0, 0, 2, 0}

说明

对于 arr[0]，右侧有三个元素更小。
对于 arr[1]，右侧有 0 个元素更小。
对于 arr[2]，右侧有 0 个元素更小。
对于 arr[3]，右侧有两个元素更小。
对于 arr[4]，右侧有 0 个元素更小。

方法 1：暴力法

在此方法中，我们将创建一个名为 countSmaller[] 的数组，并将每个元素右侧的较小元素存储起来，这将是解决此问题的暴力法。
对于每个元素，将使用嵌套的 for 循环计算右侧较小元素的数量。
每当当前元素右侧出现一个元素时，我们都会增加计数。当循环完成时，我们将 countSmaller[i] 赋值为该计数的值。
在两个循环完成后，将打印 countSmaller 数组。

C++ 实现

#include <iostream>
using namespace std;

// Function to count smaller elements on the right side of the array
void countSmallerElementsOnRightSide(int arr[], int n)
{
    // To store the count for every element
    int countSmaller[n] = {};

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // If the condition is true, increment the corresponding index value in the countSmaller array
            if (arr[i] > arr[j])
            {
                countSmaller[i]++;
            }
        }
    }

    // Print the countSmaller array
    for (int i = 0; i < n; i++)
    {
        cout << countSmaller[i] << " ";
    }
    cout << endl;
}

int main()
{
    int arr[] = {15, 10, 18, 5, 8, 11};
    int n = 6;
    countSmallerElementsOnRightSide(arr, n);
    return 0;
}

输出

4 2 3 0 0 0

方法 2：使用自平衡 BST

我们将使用自平衡 BST 以 O(N(log(n))) 的时间复杂度解决此问题。
我们将从左到右遍历数组以将这些组件添加到树中。
插入新键时，我们将首先将其与根节点进行比较。如果键大于根节点，则根节点左子树的所有节点都将大于该键。
因此，我们将通过 左子树 的大小来增加要插入键的较小元素的数量。
我们将递归地对树的所有节点重复此过程。

C++ 实现

// C++ code for counting smaller elements on the right side
#include <bits/stdc++.h>
using namespace std;

// AVL tree node
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;

    // to store the size of tree
    int size;
};

// function to get the hieght of the tree
int height(struct node *N)
{
    if (N == NULL)
        return 0;

    return N->height;
}

// function to get the size of the tree
int size(struct node *N)
{
    if (N == NULL)
        return 0;

    return N->size;
}

// function to get max of two numbers
int max(int a, int b)
{
    return (a > b) ? a : b;
}

// function create a new node in the tree
struct node *newNode(int key)
{
    struct node *node = (struct node *)
        malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;

    // initially the new node
    // is added on leaf
    node->height = 1;
    node->size = 1;
    return (node);
}

// function to right rotate the subtree rooted with r
struct node *rightRotate(struct node *r)
{
    struct node *x = r->left;
    struct node *y = x->right;

    // perform the rotation
    x->right = r;
    r->left = y;

    // update the heights
    r->height = max(height(r->left), height(r->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // update the size
    r->size = size(r->left) + size(r->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;

    // return the root
    return x;
}

// function to right rotate the subtree rooted with r
struct node *leftRotate(struct node *r)
{
    struct node *x = r->right;
    struct node *y = x->left;

    // perform the rotation
    x->left = r;
    r->right = y;

    // update the heights
    r->height = max(height(r->left), height(r->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // update the size
    r->size = size(r->left) + size(r->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;

    // return the root
    return x;
}

// function to get the balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
        return 0;

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

// function to insert a new key in the tree rooted with the node
// also updates the count of smaller elements for the new key
struct node *insert(struct node *node, int key, int *count)
{
    // 1. First perform the normal rotation
    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);

        // to update the count of smaller elments for the key
        *count = *count + size(node->left) + 1;
    }

    // 2. Now, update the hieght and size of the ancestor node
    node->height = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;

    // 3. After that, get the balance factor of the ancestor node
    int balance = getBalance(node);

    // if the node becomes unbalanced then,

    // left left case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // right right case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // left right case
    if (balance > 1 && key > node->left->key)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // right left case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

// function to update the countSmaller[] array
void constructLowerArray(int arr[], int countSmaller[], int n)
{
    struct node *root = NULL;

    for (int i = 0; i < n; i++)
        countSmaller[i] = 0;

    // start from the rightmost element, and then insert
    // all the elments one by one in the AVL tree and
    // then get the count of the smaller elements
    for (int i = n - 1; i >= 0; i--)
    {
        root = insert(root, arr[i], &countSmaller[i]);
    }
}

// function the print the array
void printArray(int arr[], int size)
{
    cout << endl;

    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
}

// Driver code
int main()
{
    int arr[] = {5, 3, 6, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    constructLowerArray(arr, l, n);

    printArray(l, n);

    return 0;
}

输出

Input: arr[] = {5, 3, 6, 1, 9}  
Output: 2 1 1 0 0

方法 3：带有两个附加字段的 BST

二叉搜索树 将包含两个附加字段，其中包括：一个字段将存储节点左侧的元素，第二个字段将存储它们的频率。
这些元素将通过从右到左遍历数组添加到树中。
当插入新键时，将计算小于当前元素的项目数。我们只需计算当前节点左侧的组件数量及其频率之和即可。
一旦元素处于正确位置，我们就可以计算其和。
将对树中的每个节点重复此过程。

程序

#include <bits/stdc++.h>
using namespace std;

// BST node structure
struct Node
{
    int val, count;
    Node *left, *right;

    // Constructor
    Node(int num1, int num2)
    {
        this->left = this->right = NULL;
        this->count = num2;
        this->val = num1;
    }
};

// Function to add a node
int addNode(Node *&root, int countSmaller, int value)
{
    // Base case
    if (root == NULL)
    {
        root = new Node(value, 0);
        return countSmaller;
    }
    if (root->val < value)
    {
        return root->count + addNode(root->right, countSmaller + 1, value);
    }
    else
    {
        root->count++;
        return addNode(root->left, countSmaller, value);
    }
}

int main()
{
    int arr[] = {12, 9, 14, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans[n] = {};

    Node *root = NULL;

    for (int i = n - 1; i >= 0; i--)
        ans[i] = addNode(root, 0, arr[i]);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    return 0;
}

输出

4 2 4 1 1 0

结论

在本文中，讨论了计算右侧较小元素的问题。我们研究了解决此问题的三种方法：暴力法、自平衡 BST，以及最后一种方法，它也是最优的，但采用了带有两个附加字段的 BST。

下一主题C++ 中数组的平衡索引

C++ 中查找右侧较小元素的数量

示例

方法 1：暴力法

方法 2：使用自平衡 BST

方法 3：带有两个附加字段的 BST

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中查找右侧较小元素的数量

示例

方法 1：暴力法

方法 2：使用自平衡 BST

方法 3：带有两个附加字段的 BST

结论

相关帖子

C++ 程序使用 DFS 查找岛屿数量

C++ 设计模式

C++ munmap_chunk 无效指针

使用 Kruskal 算法的最小生成树（C++）

C++ 按引用传递

C++ 哈密顿环检测

C++ 密码验证

如何在 C++ 中创建新线程

C++ 迭代器失效

C++ isprint()

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题