C++ 中同一数组中每个元素的下限
c++server side programmingprogramming更新于 2025/5/31 9:22:17
在这个问题中，我们给出了一个整数元素数组 arr[]。我们的任务是创建一个程序来查找同一数组中每个元素的下限。 如果元素的下限存在，我们将打印下限，否则打印 -1。
数组中元素的下限是数组中小于或等于元素的最接近元素。
让我们举一个例子来理解这个问题
输入:arr[] = {3, 1, 5 ,7, 8, 2}
输出:2 -1 3 5 7 1
解决方法
解决问题的一种方法是使用嵌套循环。一个循环遍历数组的每个元素，另一个内部循环查找数组中元素的下限。
另一种解决问题的方法是使用额外的数组来存储排序后的数组。然后循环遍历原始数组，并使用二分搜索算法查找排序后数组中元素的下限。
示例
程序说明我们的解决方案的工作原理
#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<<"给定数组的每个元素的 Floor 为 ";
printFloorEle(arr, n);
return 0;
}
输出
给定数组的每个元素的 Floor 为 2 -1 3 5 7 1
