Đếm phần tử nhỏ hơn hoặc bằng giá trị cho trước trong mảng xoay đã sắp xếp trong C++

Chúng ta được cho một mảng số nguyên. Mảng là mảng xoay đã sắp xếp (sorted rotated array). Mục tiêu là tìm số phần tử trong mảng bằng hoặc nhỏ hơn số K cho trước.

Cách tiếp cận là duyệt toàn mảng và đếm các phần tử nhỏ hơn hoặc bằng K.

Ví dụ

Đầu vào

Arr[] = { 1, 2, 3, 4, 9, 8, 10 } K = 4

Đầu ra

Phần tử <= 4: 4

Giải thích − Phần tử <= 4 là 1, 2, 3, 4. Count = 4.

Đầu vào

Arr[] = { 5, 3, 6, 1, 8, 100, 12, 31 } K = 3

Đầu ra

Phần tử <= 3: 2

Giải thích − Phần tử <= 3 là 1, 3. Count = 2.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số, K là một số.
• Số nguyên 'n' lưu độ dài mảng.
• Biến count lưu số lượng số <= K.
• Duyệt mảng một lần từ phần tử đầu (chỉ số 0).
• Nếu phần tử hiện tại <= K thì tăng count.
• Count chứa kết quả mong muốn.
• Hiển thị kết quả.

Ví dụ mã nguồn

#include <iostream> 
using namespace std; 

int main() { 
    int Arr[] = { 4, 5, 8, 1, 3, 7, 10, 9, 11 }; 
    int k = 7; 
    int n = sizeof(Arr) / sizeof(Arr[0]); 
    int count = 0; 
    for (int i = 0; i < n; i++) 
        if (Arr[i] <= k) 
            count++; 
    std::cout << "Phần tử <= " << k << " trong mảng xoay đã sắp xếp: " << count; 
    return 0; 
}

Kết quả

Phần tử <= 7 trong mảng xoay đã sắp xếp: 5