資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：統計陣列中大於其左側所有元素且大於其右側至少K個元素的元素個數
字串是一個物件，它表示一系列資料字元。字串是資料容器，始終以文字格式表示。它也用於概念、比較、分割、連線、替換、修剪、長度、內部化、相等、比較、子字串操作。使用快速排序分割槽演算法查詢陣列中最大的K個（或最小的K個）元素。
這裡有一個包含N個不同整數的陣列R[]。任務是找到那些嚴格大於其前面所有元素且嚴格大於其右側至少K個元素的特定元素。問題陳述如下：給定一個包含N個不同元素的陣列arr[ ]（陣列R）和整數K；我們必須找出有多少個元素大於其左側所有元素，且大於其右側至少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樹從右到左遍歷陣列。AVL樹生成一個數組countSmaller[]。這裡的時間複雜度為O(NlogN)，輔助空間為O(N)。對於每個滿足條件的元素，計數器加1。
讓我們找出陣列中大於其左側所有元素且大於其右側至少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個（或最小的K個）元素。
方法2 − 高效的方法來查詢陣列中最大的K個（或最小的K個）元素。
使用排序查詢最大的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個（或最小的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個元素的元素個數。
488 次瀏覽
