資料結構
網路
關係資料庫管理系統 (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+
廣告