题目:给出一个元素无序的数组,求出一个数,使得其左边的数都小于它,右边的数都大于等于它。
举例:[1,2,3,1,2,0,5,6],返回下标6(数字为5)。
思路:
time complexity:O(n) space complexity:O(1)
int findnum(vector& nums){
if(nums.empty()) return -1;
int cur = 0; //当前符合条件的元素下标
int maxv = nums[0]; //目前已遍历数组的最大值
bool flag = true; //当前遍历到的元素是否符合条件
for(int i = 1; i < nums.size(); ++ i){
if(flag && nums[i] < nums[cur]) flag = false;
if(!flag && maxv <= nums[i]){
flag = true;
cur = i;
}
maxv = max(maxv, nums[i]);
}
return flag ? cur : -1;
}
进阶题目:一个int 数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
举例:[1,2,3,1,2,0,5,5] : 输出[5,5]
思路:1.构建辅助数组min_right[i],表示子数组nums[i...n-1]中的最小值;2.定义maxv表示从左到右遍历nums数组过程中的最大值;3.当maxv == min_right[i]时符合条件。
time complexity:O(n) space complexity:O(n)
vector specialnum(vector &nums){
vector res;
if(nums.empty()) return res;
int n = nums.size();
vector min_right(n);
min_right[n-1] = nums[n-1];
for(int i = n - 2; i >= 0; -- i){
min_right[i] = nums[i] < min_right[i+1] ? nums[i] : min_right[i+1];
}
int maxv = nums[0];
for(int i = 1; i < n; ++ i){
maxv = nums[i] > maxv ? nums[i] : maxv;
if(maxv == min_right[i]) res.push_back(maxv);
}
for(int i = 0; i < res.size(); ++ i){
cout << res[i] << ' ';
}
return res;
}
如果觉得《编程判断元素归类_编程:找出所有符合条件的元素》对你有帮助,请点赞、收藏,并留下你的观点哦!