字串是一個對象,它表示資料字元的序列。字串是始終表示為文字格式的資料容器。它也用於概念、比較、拆分、連接、替換、修剪、長度、實習、等於、比較、子字串操作。使用快速排序分區演算法的陣列中的 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 個數字。
#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
在此方法中,我們將按照以下步驟找出結果 -
開始。
從右向左遍歷陣列。
插入 AVL 樹中的所有元素。
產生陣列 countSmaller[]。
每個陣列元素右側較小元素的計數。
如果是最大值,則countSmaller[i]大於等於K。
然後增加計數。
列印該值。
結束。
#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 個元素。
以上是C++程序,用於計算數組元素大於其左側所有元素且至少有K個元素在其右側的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章!