Rentetan ialah objek yang mewakili jujukan aksara data. Rentetan ialah bekas data yang sentiasa diwakili dalam format teks. Ia juga digunakan untuk konsep, perbandingan, belah, gabung, ganti, potong, panjang, interning, sama, perbandingan, operasi subrentetan. Elemen K terbesar (atau terkecil) dalam tatasusunan menggunakan algoritma pembahagian quicksort.
Ini ialah tatasusunan R[] yang mengandungi N integer berbeza. Tugasnya adalah untuk mencari elemen khusus yang lebih besar daripada semua elemen sebelumnya dan lebih besar daripada sekurang-kurangnya elemen K di sebelah kanannya. Masalahnya menyatakan bahawa tatasusunan arr[ ] (tatasusunan R) terdiri daripada N elemen berbeza dan integer K kita mesti mencari bilangan elemen yang lebih besar daripada semua elemen di sebelah kirinya dan mempunyai sekurang-kurangnya unsur K di sebelah kanannya .
Input: R[] = {16,07,10,22,2001,1997}, K = 3
Output: 16
Therefore, the count is 2.
Salin selepas log masuk
Terdapat dua cara untuk mencari elemen tatasusunan yang lebih besar daripada semua elemen di sebelah kiri dan sekurang-kurangnya elemen K di sebelah kanan.
Kaedah naif - Ini adalah cara paling mudah untuk mengulangi tatasusunan tertentu. Dalam kaedah ini kita perlu melintasi semua elemen ke kiri untuk memeriksa sama ada ia lebih kecil. Jika tidak, rentasi ke kanan dan semak sama ada unsur K terkecil adalah lebih kecil. Untuk pendekatan ini, kerumitan masa ialah O(N2) dan ruang tambahan ialah O(1).
Kaedah Cekap - Ini adalah proses pengoptimuman yang boleh dilakukan dengan BST pengimbangan diri. Lintas tatasusunan satu demi satu dari kanan ke kiri melalui Pokok AVL. Pokok AVL menjana kiraan tatasusunanSmaller[]. Kerumitan masa di sini ialah O(NlogN) dan ruang tambahan ialah O(N). Untuk setiap elemen yang memenuhi syarat, tambahkan kiraan.
Mari kita cari bilangan elemen tatasusunan yang lebih besar daripada semua elemen di sebelah kirinya dan sekurang-kurangnya elemen K di sebelah kanannya.
Algoritma untuk mengira elemen tatasusunan yang lebih besar daripada semua elemen:-
Dalam algoritma ini, kami akan mengikuti proses langkah demi langkah untuk mengira bilangan elemen tatasusunan. Dengan ini, kami akan membina beberapa kod C++ untuk mencari elemen terbesar antara semua elemen.
Langkah 1 - Bermula.
Langkah 2 - Lintas tatasusunan dari kanan ke kiri.
Langkah 3 - Masukkan semua elemen ke dalam pokok AVL.
Langkah 4 - Hasilkan kiraan tatasusunan Lebih Kecil[] dengan menggunakan pepohon AVL.
Langkah 5 - Ia mengandungi kiraan elemen yang lebih kecil di sebelah kanan setiap elemen tatasusunan.
Langkah 6 - Gelung melalui tatasusunan dan cari setiap elemen.
Langkah 7 - Semak sama ada ini adalah nilai maksimum yang diperolehi setakat ini dan jika countSmaller[i] lebih besar daripada atau sama dengan K.
Langkah 8 - Jika syarat dipenuhi, tambahkan kiraan.
Langkah 9 - Cetak nilai akhir kiraan sebagai jawapan.
Langkah 10 - Penamatan.
Tatabahasa
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;
}
Salin selepas log masuk
Berikut ialah nombor tatasusunan integer, integer ialah K. Ia akan mengembalikan elemen Kth dalam tatasusunan. Kita perlu menyelesaikannya dalam kerumitan masa O(n).
Kaedah
Cari K elemen terbesar (atau terkecil) menggunakan pengisihan
Kita boleh mendapatkan hasil daripada masalah ini dengan menyusun. Berikut adalah langkah-langkahnya -
Contoh 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>Salin selepas log masuk
Output
2022 2001 1997
Salin selepas log masuk
Cara yang cekap untuk mencari elemen K terbesar (atau terkecil) dalam tatasusunan
Dalam kaedah ini kita akan mengikuti langkah berikut untuk mengetahui hasilnya -
Mula.
Lintas tatasusunan dari kanan ke kiri.
Masukkan semua elemen dalam pokok AVL.
Jana kiraan tatasusunan Lebih Kecil[].
Kiraan elemen yang lebih kecil di sebelah kanan setiap elemen tatasusunan.
Jika ia adalah nilai maksimum, countSmaller[i] lebih besar daripada atau sama dengan K.
Kemudian tingkatkan kiraan.
Cetak nilai.
Akhirnya.
Contoh 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;
}
Salin selepas log masuk
Output
2
Salin selepas log masuk
Kesimpulan
Jadi kita tahu cara menulis kod C++ untuk mengira bilangan elemen tatasusunan yang lebih besar daripada semua elemen di sebelah kirinya dan sekurang-kurangnya elemen K di sebelah kanannya.
Atas ialah kandungan terperinci Program C++ untuk mengira bilangan elemen tatasusunan yang lebih besar daripada semua elemen di sebelah kirinya dan mempunyai sekurang-kurangnya elemen K di sebelah kanannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
