极客教程C++程序 统计大于数组左侧所有元素且至少有K个右侧元素小于其的数组元素
给定一个由 N 个不同整数组成的数组 A[ ] ，任务是找到所有满足以下条件的数组元素的数量：比左侧所有元素都 严格大于 ，且其右侧 至少 有 K 个元素小于它。
示例:
输入: A[] = {2, 5, 1, 7, 3, 4, 0}, K = 3
输出: 2
解释:
满足给定条件的唯一数组元素为：
- 5 ：比左侧元素{2}都大，其右侧 至少 有K(=3)个元素小于它{1,3,4,0}
- 7 ：比左侧元素{2,5,1}都大，其右侧 至少 有K(=3)个元素小于它{3,4,0}
因此，计数器为2。
输入: A[] = {11, 2, 4, 7, 5, 9, 6, 3}, K = 2
输出: 1
朴素方法:
解决此问题的最简单方法是遍历整个数组并为每个元素遍历其左侧的所有元素以检查它们是否都小于当前元素，并遍历其右侧的所有元素以检查 至少 有K个元素是否小于当前元素。 对于满足条件的每个元素，增加计数器。最后，输出计数器值。
下面是实现上述想法的程序：
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number
// of elements which are greater
// than all elements on its left
// and K elements on its right
int countElements(int arr[], int n, int K)
{
int result = 0;
for (int i = 0; i < n; i++) {
bool leftGreater = true;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
leftGreater = false;
break;
}
}
if (leftGreater) {
int count = 0;
for (int l = i + 1; l < n; l++) {
if (arr[i] > arr[l]) {
count++;
}
}
if (count >= K)
result++;
}
}
return result;
}
// Driver Code
int main()
{
int A[] = { 2, 5, 1, 7, 3, 4, 0 };
int n = sizeof(A) / sizeof(int);
int K = 3;
cout << countElements(A, n, K);
return 0;
}
输出
2
时间复杂度： O（N 2）
辅助内存： O（1）
高效做法：
可以通过使用自平衡二叉树进一步优化上述方法。按照以下步骤进行：
- 从右到左遍历数组，在 AVL 树中逐一插入所有元素。
- 使用 AVL 树生成一个数组 countSmaller[] ，其中包含每个数组元素右侧较小元素的计数。
- 遍历数组，对于每个第 i 个元素，检查它是否是目前为止获得的最大值，以及 countSmaller[i] 是否大于等于 K 。
- 如果是，增加 count 。
- 将 count 的最终值作为答案打印出来。
以下是上述方法的实现：
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of an AVL Tree Node
struct node {
int key;
struct node* left;
struct node* right;
int height;
// Size of the tree rooted
// with this node
int size;
};
// Utility function to get maximum
// of two integers
int max(int a, int b);
// Utility function to get height
// of the tree rooted with N
int height(struct node* N)
{
if (N == NULL)
return 0;
return N->height;
}
// Utility function to find size of
// the tree rooted with N
int size(struct node* N)
{
if (N == NULL)
return 0;
return N->size;
}
// Utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Helper function to allocates a
// new node with the given key
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);
}
// Utility function to right rotate
// subtree rooted with y
struct node* rightRotate(struct node* y)
{
struct node* x = y->left;
struct node* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right))
+ 1;
x->height = max(height(x->left),
height(x->right))
+ 1;
// Update sizes
y->size = size(y->left)
+ size(y->right) + 1;
x->size = size(x->left)
+ size(x->right) + 1;
// Return new root
return x;
}
// Utility function to left rotate
// subtree rooted with x
struct node* leftRotate(struct node* x)
{
struct node* y = x->right;
struct node* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right))
+ 1;
y->height = max(height(y->left),
height(y->right))
+ 1;
// Update sizes
x->size = size(x->left)
+ size(x->right) + 1;
y->size = size(y->left)
+ size(y->right) + 1;
// Return new root
return y;
}
// Function to obtain 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 to the
// tree rooted with node
struct node* insert(struct node* node, int key,
int* count)
{
// Perform the normal BST 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);
// Update count of smaller elements
*count = *count + size(node->left) + 1;
}
// Update height and size of the ancestor
node->height = max(height(node->left),
height(node->right))
+ 1;
node->size = size(node->left)
+ size(node->right) + 1;
// Get the balance factor of the ancestor
int balance = getBalance(node);
// 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 generate an array which contains
// count of smaller elements on the right
void constructLowerArray(int arr[],
int countSmaller[],
int n)
{
int i, j;
struct node* root = NULL;
for (i = 0; i < n; i++)
countSmaller[i] = 0;
// Insert all elements in the AVL Tree
// and get the count of smaller elements
for (i = n - 1; i >= 0; i--) {
root = insert(root, arr[i],
&countSmaller[i]);
}
}
// Function to find the number
// of elements which are greater
// than all elements on its left
// and K elements on its right
int countElements(int A[], int n, int K)
{
int count = 0;
// Stores the count of smaller
// elements on its right
int* countSmaller
= (int*)malloc(sizeof(int) * n);
constructLowerArray(A, countSmaller, n);
int maxi = INT_MIN;
for (int i = 0; i <= (n - K - 1); i++) {
if (A[i] > maxi && countSmaller[i] >= K) {
count++;
maxi = A[i];
}
}
return count;
}
// Driver Code
int main()
{
int A[] = { 2, 5, 1, 7, 3, 4, 0 };
int n = sizeof(A) / sizeof(int);
int K = 3;
cout << countElements(A, n, K);
return 0;
}
输出
2
时间复杂度： O(NlogN)
辅助空间： O(N)