資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中列印排序陣列中形成等差數列的所有三元組
在這個問題中，我們給定一個排序好的數字陣列，我們需要找到形成等差數列的三元組。
等差數列是一系列數字，其中連續項之間的差值相同。
讓我們舉一個例子來更好地理解這個問題 -
Input :
array = {2 , 5 , 7, 8 , 9 , 10}
Output :
2 5 8
5 7 9
7 8 9
8 9 10為了解決這個問題，一個簡單的解決方案是執行三個迴圈並檢查所有三元組是否為等差數列。但這種方法的時間複雜度為 n3 階。
一個更好的解決方案是使用雜湊。在這種方法中，我們將從陣列的第二個元素開始，並將每個元素視為等差數列的中間元素，並檢查它是否形成等差數列。
示例
#include <iostream>
using namespace std;
void TripletsAP(int arr[], int n){
for (int i = 1; i < n - 1; i++){
for (int j = i - 1, k = i + 1; j >= 0 && k < n;){
if (arr[j] + arr[k] == 2 * arr[i]){
cout<<arr[j]<<"\t"<<arr[i]<<"\t"<< arr[k] << endl;
k++;
j--;
}
else if (arr[j] + arr[k] < 2 * arr[i])
k++;
else
j--;
}
}
}
int main(){
int arr[] = {2 , 5 , 7, 8 , 9 , 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The triplets that are in AP are : \n";
TripletsAP(arr, n);
return 0;
}輸出
形成等差數列的三元組為 -
2 5 8 5 7 9 7 8 9 8 9 10
更新於: 2020-01-17
171 次瀏覽
廣告