APを形成するソートされた配列のすべてのトリプレットを出力します


難易度 ミディアム
よく聞かれる アクセンチュア アコライト ケイデンスインド Googleポリシー インフォエッジ インテュイット Pinterest
配列 ハッシュ 検索

「APを形成するソートされた配列にすべてのトリプレットを出力する」という問題は、ソートされた配列を指定したことを示しています 整数 アレイ。 タスクは、等差数列を形成する可能性のあるすべてのトリプレットを見つけることです。

APを形成するソートされた配列のすべてのトリプレットを出力します

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

説明

これらはすべてAPを形成するトリプレットです

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

説明

これらはすべてAPを形成するトリプレットです

アルゴリズム

  1. からループ i = 1からn-1(含まれていない)。
  2. jの値をiよりXNUMX小さい値に設定し、kの値をiよりXNUMX大きい値に設定します。
  3. 一方、 j> = 0 && k <n.
    1. XNUMXつの現在の配列要素の合計が他の配列要素のXNUMX倍に等しいかどうかを確認します。
      1. trueの場合、現在のXNUMXつの要素を出力し、kとjの値をそれぞれ増減します。
    2. 1つの要素の合計が別の要素のXNUMX倍未満であるかどうかを確認してから、kをXNUMX増やします。
    3. 1つの要素の合計が別の要素のXNUMX倍より大きいかどうかを確認してから、jをXNUMXつ減らします。

説明

私たちは与えました ソート 配列。 等差数列を形成できるすべてのトリプレットを見つけるように求められます。 等差数列は、すべての要素がシーケンス全体に沿ってそれらの間の特定の距離で連続して来る数列として定義できます。 2つの数の合計がXNUMX番目の数のXNUMX倍に等しい場合、a + c = XNUMXbを示すAPの式によってトリプレットを見つけます。

XNUMXつのforループとXNUMXつの配列で配列全体をトラバースします。 whileループ、 'while loop'は、XNUMXつの要素がAPを形成できるかどうかを確認します。 forループを通過するときは常に、jの値をiの値よりXNUMX小さい値に設定し、kの値をiの値よりXNUMX大きい値に設定します。 チェックする要素を取得するため、arr [i]、arr [j]、およびarr [k]をチェックするXNUMXつの要素があるたびに、i、j、およびkの値はそれぞれ異なります。 forループまたはinのトラバーサル whileループ.

XNUMXつの要素の合計がXNUMX番目の要素に等しいことがわかった場合、これらのXNUMXつの配列要素を出力します。これらはAPを形成できます。 アルゴリズムに従ってjとkの値を更新します。 XNUMXつの要素の合計がXNUMX番目の要素のXNUMX倍未満であることがわかった場合。 kの値を増やすか、合計がXNUMX番目の要素のXNUMX倍より大きいことがわかった場合は、jの値を減らします。 これは、配列全体をトラバースして、APを形成できるすべての可能な要素を見つけるまで続きます。

コード

APを形成するソートされた配列のすべてのトリプレットを出力するC ++コード

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

APを形成するソートされた配列のすべてのトリプレットを出力するJavaコード

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

複雑さの分析

時間の複雑さ

オン2where 「n」  配列内の要素の数です。 最初のループが最後に到達するまで実行され、次にXNUMX番目のネストされたループがAPの要素を見つけるために使用されるXNUMXつのネストされたループがあるためです。

スペースの複雑さ

O(1) 余分なスペースは必要ありません。