ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขององค์ประกอบจำนวนเต็ม ภารกิจของเราคือการสร้างโปรแกรมหา Floor ของทุกองค์ประกอบในอาร์เรย์เดียวกัน หาก floor ขององค์ประกอบมีอยู่ เราจะพิมพ์ floor มิฉะนั้นพิมพ์ -1
Floor ขององค์ประกอบในอาร์เรย์ คือองค์ประกอบที่ใกล้ที่สุดซึ่งน้อยกว่าหรือเท่ากับองค์ประกอบในอาร์เรย์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: arr[] = {3, 1, 5 ,7, 8, 2} Output: 2 -1 3 5 7 1
วิธีการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการใช้ nested loops หนึ่งสำหรับลูปแต่ละองค์ประกอบของอาร์เรย์ และอีกอันสำหรับหา floor ขององค์ประกอบในอาร์เรย์
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้อาร์เรย์เพิ่มเติมเพื่อเก็บอาร์เรย์ที่จัดเรียงแล้ว จากนั้นลูปผ่านอาร์เรย์เดิมและหา floor ขององค์ประกอบในอาร์เรย์ที่จัดเรียงแล้วโดยใช้ binary search algorithm
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
