資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中查詢排序陣列中和小於x的數對
給定一個整數型別的排序陣列和一個整數變數x，任務是從給定陣列中形成數對，計算數對中元素的和，並檢查計算出的和是否小於x。
輸入 − int arr[] = {2, 7, 1, 0, 8}, int x = 8
輸出 − 排序陣列中和小於x的數對的數量為 - 4
解釋 − 從給定陣列中可以形成的數對有：(2, 7) = 9（大於x），(2, 1) = 3（小於x），(2, 0) = 2（小於x），(2, 8) = 10（大於x），(7, 1) = 8（等於x），(7, 0) = 7（小於x），(7, 8) = 15（大於x），(1, 0) = 1（小於x），(1, 8) = 8（等於x），(0, 8) = 8（等於x）。所以和小於x的數對是(4, 0)和(2, 2)。因此，和小於x的數對的數量為4。
輸入 − int arr[] = {2, 4, 6, 8}, int x = 10
輸出 − 排序陣列中和小於x的數對的數量為 - 2
解釋 − 從給定陣列中可以形成的數對有：(2, 4) = 6（小於x），(2, 6) = 8（小於x），(2, 8) = 10（等於x），(4, 6) = 10（等於x），(4, 8) = 12（大於x），(6, 8) = 14（大於x）。所以，和小於x的數對的數量為2。
下面程式中使用的演算法如下
解決給定問題有多種方法，即樸素方法和高效方法。因此，讓我們首先看看樸素方法。
輸入一個整數元素陣列，計算陣列的大小並將資料傳遞給函式
宣告一個臨時變數count來儲存和小於x的數對的數量。
從i=0開始，迴圈FOR到陣列的大小
在迴圈內部，從j=i+1開始，另一個迴圈FOR到陣列的大小
在迴圈內部，計算和為arr[i] + arr[j]，並檢查IF sum < x，則將count加1。
返回count
列印結果。
高效方法
輸入一個整數元素陣列，計算陣列的大小並將資料傳遞給函式
宣告一個臨時變數count來儲存和小於x的數對的數量。
將arr_0設定為0，將arr_1設定為size-1
從arr_0開始，迴圈FOR到arr_1
在迴圈內部，檢查IF arr[arr_0] + arr[arr_1] < x，則將count設定為count + (arr_1 - arr_0)並遞增arr_0++，否則將arr_1減1
返回count
列印結果。
示例（樸素方法）
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
int count = 0;
int sum = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
sum = arr[i] + arr[j];
if(sum < x){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of pairs in a sorted array whose sum is less than x are: 4
示例（高效方法）
#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
while(arr_0 < arr_1){
if (arr[arr_0] + arr[arr_1] < x){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {2, 7, 1, 0, 8};
int size = sizeof(arr) / sizeof(arr[0]);
int x = 8;
cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of pairs in a sorted array whose sum is less than x are: 4
568 次瀏覽
