在C ++中以排序数组的形式打印所有三胞胎
在这个问题中,我们得到了一个数字排序的数组,我们需要找到具有三元组的三进位数,它们都是算术级数的形式。
算术级数是一系列数字,其中连续项之间的差是相同的。
让我们举个例子来更好地理解问题-
Input : array = {2 , 5 , 7, 8 , 9 , 10} Output : 2 5 8 5 7 9 7 8 9 8 9 10
为了解决此问题,一个简单的解决方案是运行三个循环并检查所有三连音是否在AP中。但是该方法的时间复杂度约为n3。
更好的解决方案是使用哈希。在此方法中,我们将从数组的第二个元素开始,将每个元素视为AP的中间元素,然后检查它是否构成AP。
示例
#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; }
输出结果
AP中的三元组为-
2 5 8 5 7 9 7 8 9 8 9 10