Chúng ta được cung cấp một mảng các số nguyên có kích thước N. Các biến L và R xác định một phạm vi từ 1 đến N. Mục tiêu là tìm số phần tử nhỏ nhất nằm trong phạm vi L và R sao cho L> =1 và R <=N.
-
Chúng tôi sẽ làm điều này bằng cách duyệt qua các phần tử nằm trong phạm vi L và R và tìm phần tử nhỏ nhất.
-
Một lần nữa, duyệt qua các phần tử của phạm vi L và R và đếm số gia tăng nếu bất kỳ phần tử nào bằng với giá trị nhỏ nhất được tính ở bước 1.
Hãy cùng hiểu với các ví dụ.
Đầu vào - arr [] ={1,2,3,0,3,2,0,1}, N =8, L =2, R =5
Đầu ra - Đếm số nhỏ nhất trong phạm vi - 1
Giải thích -
Các phần tử trong phạm vi L (1) đến R (5) là arr [1] đến arr [4]. {2,3,0,3}. Giá trị nhỏ nhất là 0. Tổng số 0 là 1.
Đầu vào - arr [] ={1,2,3,0,3,2,0,1}, N =8, L =3, R =8
Đầu ra - Đếm số nhỏ nhất trong phạm vi - 2
Giải thích -
Các phần tử trong phạm vi L (3) đến R (8) là arr [2] đến arr [7]. {3,0,3,2,0,1}. Giá trị nhỏ nhất là 0. Tổng số 0 là 2.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên arr [] được khởi tạo với các số ngẫu nhiên.
-
Các số nguyên L và R đại diện cho phạm vi bên trong arr []. Count lưu trữ số lượng nhỏ nhất trong phạm vi L và R.
-
Hàm countSmallest (int arr [], int n, int l, int r) nhận một mảng, độ dài của nó, L và R làm đầu vào và trả về số đếm nhỏ nhất trong phạm vi.
-
Khởi tạo phần tử nhỏ nhất =arr [l], ngoài cùng bên trái và số lượng ban đầu của phần tử nhỏ nhất là 0.
-
Bây giờ nếu l <0 và r> =n thì trả về 0, đã cung cấp dải ô không hợp lệ.
-
Bắt đầu duyệt qua mảng từ chỉ mục l-1 đến r-1. Cập nhật nhỏ nhất nếu arr [i]
-
Một lần nữa, duyệt qua mảng từ l-1 đến r-1, nếu arr [i] ==nhỏ nhất, số gia tăng.
-
Số lượt trả về là kết quả mong muốn.
-
Bên trong main, hiển thị kết quả có trong số đếm.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
// Function to find if number is prime
int countSmallest(int arr[],int n,int l, int r){
int smallest=arr[l];
int count=0;
if(l<0 && r>=n)
return 0;
for(int i=l-1;i<r;i++){
if(arr[i]<=smallest){
smallest=arr[i];
}
}
for(int i=l-1;i<r;i++){
if(arr[i]==smallest){
++count;
}
}
return count;
}
int main(){
int arr[] = { 3,2,1,1,2,3 };
int n = 6;
int L,R;
int count=0;
L=1,R=5;
count=countSmallest(arr,n,L,R);
cout<<endl<<"Count of number of smallest in given range:"<<count;
L=3,R=4;
count=countSmallest(arr,n,L,R);
cout<<endl<<"Count of number of smallest in given range:"<<count;
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of smallest in given range:2 Count of number of smallest in given range:2