Tầng của mọi phần tử trong cùng một mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm các phần tử nguyên. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tầng của mọi phần tử trong cùng một mảng. Nếu tầng của một phần tử tồn tại, chúng ta sẽ in tầng nếu không thì in -1.

Tầng của một phần tử trong mảng là phần tử gần nhất nhỏ hơn hoặc bằng phần tử trong mảng.

Hãy lấy một ví dụ để hiểu vấn đề

Input: arr[] = {3, 1, 5 ,7, 8, 2}
Output: 2 -1 3 5 7 1

Phương pháp tiếp cận giải pháp

Một cách tiếp cận để giải quyết vấn đề là sử dụng các vòng lặp lồng nhau. Một để lặp phần tử phía trước của mảng và phần tử bên trong để tìm tầng của phần tử trong mảng.

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng một mảng bổ sung để lưu trữ mảng đã sắp xếp. Sau đó lặp lại mảng ban đầu đó và tìm tầng của phần tử trong mảng đã sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

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

void printFloorEle(int arr[], int n){
   vector<int> sortedArr(arr, arr + n);
   sort(sortedArr.begin(), sortedArr.end());
   for (int i = 0; i < n; i++) {
      if (arr[i] == sortedArr[0]) {
         if (arr[i] == sortedArr[1])
            cout<<arr[i];
         else
            cout<<-1;
         cout<<"\t";
         continue;
      }
      auto iterator = lower_bound(sortedArr.begin(),sortedArr.end(), arr[i]);
      if (iterator != sortedArr.end() && *(iterator + 1) == arr[i])
         cout<<arr[i]<<"\t";
      else
         cout<<*(iterator - 1)<<"\t";
   }
}
int main(){
   int arr[] = { 3, 1, 5 ,7, 8, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The Floor of every element of the given array is ";
   printFloorEle(arr, n);
   return 0;
}

Đầu ra

The Floor of every element of the given array is 2 -1 3 5 7
1