C++ 程序计算大于其左侧所有元素且至少大于其右侧 K 个元素的数组元素
字符串是一个对象，它表示一系列数据字符。字符串是始终以文本格式表示的数据容器。它还用于概念、比较、拆分、连接、替换、修剪、长度、实习、等于、比较、子字符串操作。使用快速排序分区算法对数组中的 K 个最大(或最小)元素进行排序。
这是一个具有 N 个不同整数的数组 R[]。任务是找到严格大于其前面的所有元素并且严格大于其右侧至少 K 个元素的特定元素。问题指出一个包含 N 个不同元素和整数 K 的数组 arr[ ](数组 R)；我们必须找出一个大于其左侧所有元素且至少大于其右侧 K 个元素的元素数。
输入:R[] = {16,07,10,22,2001,1997}, K = 3
输出:16
因此，计数为 2。
有两种方法可以找出大于其左侧所有元素且至少大于其右侧 K 个元素的数组元素。
朴素方法 - 这是遍历特定数组的最简单方法。在此方法中，我们必须遍历左侧的所有元素以检查它是否较小。否则，向右遍历它们以检查最小 K 个元素是否较小。对于这种方法，时间复杂度为 O(N2)，辅助空间为 O(1)。
高效方法 - 这是一个可以通过自平衡 BST 完成的优化过程。通过 AVL 树从右到左逐个遍历数组。AVL 树生成一个数组 countSmaller[]。这里的时间复杂度为 O(NlogN)，辅助空间为 O(N)。对于每个满足条件的元素，增加计数。
让我们找出左侧大于所有元素且右侧至少有 K 个元素的数组元素的数量。
用于计算大于所有元素的数组元素的算法:-
在此算法中，我们将按照分步过程来计算数组元素。通过这种方式，我们将构建一些 C++ 代码来查找所有元素中最大的元素。
步骤 1 - 开始。
步骤 2 - 从右到左遍历数组。
步骤 3 - 将所有元素插入 AVL 树中。
步骤 4 - 通过使用 AVL 树生成数组 countSmaller[]。
步骤 5 - 它包含每个数组元素右侧较小元素的数量。
步骤 6 - 遍历数组并遍历每个元素。
步骤 7 - 检查它是否是迄今为止获得的最大值，并且 countSmaller[i] 是否大于或等于 K。
步骤 8 - 如果条件满足，则增加计数。
步骤 9 − 打印计数的最终值作为答案。
步骤 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());
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);
}
输出
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;
}
输出
2
结论
这样我们就知道如何编写 C++ 代码来计算大于其左侧所有元素且右侧至少 K 个元素的数组元素数。
