ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของอิลิเมนต์จำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อค้นหาพื้นของทุกองค์ประกอบในอาร์เรย์เดียวกัน หากมีพื้นขององค์ประกอบอยู่ เราจะพิมพ์พื้นไม่เช่นนั้นให้พิมพ์ -1
พื้นขององค์ประกอบในอาร์เรย์ เป็นองค์ประกอบที่ใกล้เคียงที่สุดซึ่งน้อยกว่าหรือเท่ากับองค์ประกอบในอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: arr[] = {3, 1, 5 ,7, 8, 2}
Output: 2 -1 3 5 7 1 แนวทางการแก้ปัญหา
แนวทางในการแก้ปัญหาคือการใช้การวนซ้ำซ้อน หนึ่งเพื่อวนรอบองค์ประกอบ foreach ของอาร์เรย์และอีกอันหนึ่งสำหรับค้นหาพื้นขององค์ประกอบในอาร์เรย์
อีกวิธีในการแก้ปัญหาคือการใช้อาร์เรย์พิเศษเพื่อจัดเก็บอาร์เรย์ที่จัดเรียงไว้ จากนั้นวนซ้ำอาร์เรย์เดิมนั้นและค้นหาพื้นขององค์ประกอบในอาร์เรย์ที่จัดเรียงโดยใช้อัลกอริทึมการค้นหาแบบไบนารี
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The Floor of every element of the given array is 2 -1 3 5 7 1
