Phần tử K-th nhỏ nhất sau khi loại bỏ một số nguyên từ tập số tự nhiên trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm phần tử nhỏ nhất sau khi loại bỏ một số nguyên từ tập số tự nhiên.

Cho một mảng các phần tử và giá trị K. Loại bỏ tất cả các phần tử từ tập số tự nhiên có mặt trong mảng cho trước. Sau đó tìm số nhỏ thứ K từ các số tự nhiên còn lại.

Các bước giải quyết

• Khởi tạo mảng và K.
• Khởi tạo mảng flag, gán 0 cho tất cả, gán 1 cho các phần tử có trong mảng cho trước.
• Viết vòng lặp đến kích thước mảng:
  • Giảm K nếu phần tử hiện tại không có trong mảng flag.
  • Trả về giá trị hiện tại khi K = 0.
• Trả về 0.

Ví dụ

Dưới đây là mã nguồn C++:

#include <bits/stdc++.h> 
#define MAX 1000000 
using namespace std; 

int smallestNumber(int arr[], int n, int k) { 
    int flag[MAX]; 
    memset(flag, 0, sizeof flag); 
    for (int i = 0; i < n; i++) { 
        flag[arr[i]] = 1; 
    } 
    for (int i = 1; i < MAX; i++) { 
        if (flag[i] != 1) { 
            k--; 
        } 
        if (!k) { 
            return i; 
        } 
    } 
    return 0; 
} 

int main() { 
    int k = 2; 
    int arr[] = { 3, 5 }; 
    cout << smallestNumber(arr, 2, k) << endl; 
    return 0; 
}

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

2

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.