数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告