数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中排序数组中小于或等于元素的计数
给定一个整数数组。目标是找到数组中小于或等于给定值K的元素个数。
输入
Arr[]= { 1, 2, 3, 14, 50, 69, 90 } K=12输出
Numbers smaller or equal to K: 3
解释
Numbers 1,2,3 is smaller or equal to 12.
输入
Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 } K=14输出
Numbers smaller or equal to K: 5
解释
Numbers 12, 13, 14 are smaller or equal to 14.
朴素方法
下面程序中使用的方法如下：
我们使用整数数组Arr[]和K。
函数smallorEqual(int arr[],int k,int len)返回arr[]中小于或等于K的元素个数。
将初始变量count设为0，用于统计此类数字。
使用for循环遍历数字数组。i=0到i<len
现在对于每个数字arr[i]，如果它<=k，则递增count。
在循环结束时，count将包含满足条件的总数。
返回count作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int smallorEqual(int arr[],int k,int len){
int count = 0;
for (int i = 0; i < len; i++){
if(arr[i]<=k)
{ count++; }
else
{ break; }
}
return count;
}
int main(){
int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
int K = 21;
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<"Numbers smaller or equal to K: "<<smallorEqual(Arr,K,Length);
return 0;
}输出
如果运行以上代码，将生成以下输出：
Numbers smaller or equal to K: 6
高效方法（使用二分查找）
下面程序中使用的方法如下：
我们使用整数数组Arr[]和K。
函数binarySearch(int arr[],int k,int len)返回arr[]中小于或等于K的元素个数。
取索引low=0，high=len-1和mid=(low+high)/2;
取变量index=-1;
使用while循环，直到low<=high
检查arr[mid]的值。如果它<= k，则index=mid。新的low=mid+1
否则，新的high=mid-1。
在while循环结束时，index将是最后一个数字<=k的索引。
返回index+1作为结果，因为数组索引从0开始，所有从索引0到索引的数字都小于k。
示例
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[],int k,int len){
int low = 0;
int high = len -1;
int mid = (high+low)/2;
int index = -1;
while(low <= high){
mid =( low + high ) / 2;
if(arr[mid] <= k){
index = mid;
low = mid+1;
}
else{
high=mid-1;
}
}
return (index+1);
}
int main(){
int Arr[] = { 1,5,11,12,19,21,32,53,70,100 };
int K = 21;
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<"Numbers smaller or equal to K: "<<binarySearch(Arr,K,Length);
return 0;
}输出
如果运行以上代码，将生成以下输出：
Numbers smaller or equal to K: 6
更新于：2020年10月31日
浏览量1K+
广告