C++程序，用于计算数组元素大于其左侧所有元素且至少有K个元素在其右侧的数量-C++-PHP中文网

C++程序，用于计算数组元素大于其左侧所有元素且至少有K个元素在其右侧的数量

字符串是一个对象，它表示数据字符的序列。字符串是始终表示为文本格式的数据容器。它还用于概念、比较、拆分、连接、替换、修剪、长度、实习、等于、比较、子字符串操作。使用快速排序分区算法的数组中的 K 个最大（或最小）元素。

这是一个数组 R[]，其中包含 N 个不同的整数。任务是找到那个特定元素，该元素严格大于其前面的所有元素，并且严格大于其右侧的至少 K 个元素。该问题指出，一个由 N 个不同元素和整数 K 组成的数组 arr[ ]（数组 R）；我们必须找出比其左侧所有元素都大的元素个数，并且其右侧至少有 K 个元素。

Input: R[] = {16,07,10,22,2001,1997}, K = 3
Output: 16
Therefore, the count is 2.

登录后复制

有两种方法可以找出大于左侧所有元素且右侧至少 K 个元素的数组元素。

朴素方法 - 这是遍历特定数组的最简单方法。在这个方法中，我们必须向左侧遍历所有元素来检查它是否较小。否则，向右遍历，检查最小的 K 个元素是否较小。对于这种方法，时间复杂度为 O(N2)，辅助空间为 O(1)。
高效方法 - 这是一个可以通过自平衡 BST 完成的优化过程。通过AVL Tree从右向左一一遍历数组。 AVL Tree 生成一个数组 countSmaller[]。这里时间复杂度是O(NlogN)，辅助空间是O(N)。对于满足满足条件的每个元素，增加计数。

让我们找出数组元素的数量大于其左侧所有元素且右侧至少有 K 个元素。

计算大于所有元素的数组元素的算法：-

在此算法中，我们将按照一步一步的过程来计算数组元素的数量。通过这个，我们将构建一些 C++ 代码来找到所有元素中最大的元素。

第 1 步 - 开始。
第 2 步 - 从右向左遍历数组。
第 3 步 - 将所有元素插入 AVL 树中。
第 4 步 - 通过使用 AVL 树生成数组 countSmaller[]。
第 5 步 - 它包含每个数组元素右侧较小元素的计数。
第 6 步 - 遍历数组并查找每个元素。
第 7 步 - 检查是否是迄今为止获得的最大值，并且 countSmaller[i] 是否大于或等于 K。
第 8 步 - 如果满足条件，则增加计数。
第 9 步 - 打印 count 的最终值作为答案。
第 10 步 - 终止。

语法

for (i = k; i < array.length; i++){
minIndex = 0;
for (int j = 0; j < k; j++){
   if(array[j] < array[minIndex]){
      minIndex = j;
      array[minIndex] = array[j];
   }
}
if (array[minIndex] < array[i]){
   int temp = array[minIndex];
   array[minIndex] = array[i];
   array[i] = temp;
}

登录后复制

这里是一个整数数组num，整数为K。它将返回数组中的第K个元素。我们必须以 O(n) 的时间复杂度来解决它。

方法

方法 1 - 使用排序查找 K 个最大（或最小）元素。
方法 2 - 查找数组中 K 最大（或最小）元素的有效方法。

使用排序查找 K 最大（或最小）元素

通过排序的方法我们可以得到这个问题的结果。以下是步骤 -

元素降序排序。
打印该排序数组中的前 K 个数字。

示例 1

#include <bits/stdc++.h>
using namespace std;
void kLargest(int arr[], int a, int b){
   sort(arr, arr + a, greater<int>());
   for (int i = 0; i < b; i++)
   cout << arr[i] << " ";
}
int main(){
   int arr[] = { 10, 16, 07, 2001, 1997, 2022, 50 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   kLargest(arr, n, k);
}
</int>

登录后复制

输出

2022 2001 1997

登录后复制

查找数组中 K 个最大（或最小）元素的有效方法

在此方法中，我们将按照以下步骤找出结果 -

开始。
从右向左遍历数组。
插入 AVL 树中的所有元素。
生成数组 countSmaller[]。
每个数组元素右侧较小元素的计数。
如果是最大值，则countSmaller[i]大于等于K。
然后增加计数。
打印该值。
结束。

示例 2

#include <bits/stdc++.h>
using namespace std;
struct node {
   int key;
   struct node* left;
   struct node* right;
   int height;
   int size;
};
int max(int a, int b);
int height(struct node* N){
   if (N == NULL)
   return 0;
   return N->height;
}
int size(struct node* N){
   if (N == NULL)
   return 0;
   return N->size;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
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;
}
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;
}
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){
   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;
   }
   node->height = max(height(node->left),
   height(node->right))
   + 1;
   node->size = size(node->left)
   + size(node->right) + 1;
   int balance = getBalance(node);
   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;
}
void constructLowerArray(int arr[],
int countSmaller[],
int n){
   int i, j;
   struct node* root = NULL;
   for (i = 0; i < n; i++)
      countSmaller[i] = 0;
   for (i = n - 1; i >= 0; i--) {
      root = insert(root, arr[i], &countSmaller[i]);
   }
}
int countElements(int A[], int n, int K){
   int count = 0;
   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;
}
int main(){
   int A[] = { 16, 10, 2022, 1997, 7, 2001, 0 };
   int n = sizeof(A) / sizeof(int);
   int K = 3;
   cout << countElements(A, n, K);
   return 0;
}

登录后复制