Отпечатайте всички триплети в сортиран масив, които образуват AP


Ниво на трудност M
Често задавани в Accenture Аколит Каденс Индия Google InfoEdge Intuit Pinterest
Array Хашиш Търсене

Проблемът „Отпечатване на всички тризнаци в сортиран масив, които образуват 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 и стойността на k на едно по-голямо от i.
  3. Докато j> = 0 && k <n.
    1. Проверете дали сумата от двата текущи елемента на масива е равна на два пъти от другия елемент на масива,
      1. Ако е вярно, отпечатайте текущите три елемента и намалете и увеличете съответно стойностите на k и j.
    2. Проверете дали сумата на двата елемента е по-малка от два пъти на друг елемент, след това увеличете k с 1.
    3. Проверете дали сумата на двата елемента е по-голяма от два пъти на друг елемент, след това намалете j с 1.

Обяснение

Дадохме a сортирано масив. От нас се иска да открием всички тризнаци, които могат да образуват аритметична прогресия. Аритметичната прогресия може да бъде дефинирана като числова последователност, при която всички елементи идват последователно с определено разстояние между тях по цялата последователност. Ще намерим триплета по формулата на AP, която гласи a + c = 2b, т.е. ако сумата от двете числа е равна на два пъти от третото число.

Прекоси целия масив с един за цикъл for и a докато цикъл, 'while loop' ще провери дали откриваме, че трите елемента могат да образуват AP или не. Ще зададем стойността на j на една по-малка от стойността на i и стойността на k на една повече от стойността на i, всеки път, когато преминем през цикъла for. Той ще вземе елемент, който да проверим, така че всеки път, когато имаме три елемента за проверка arr [i], arr [j] и arr [k], стойността на i, j и k, която ще варира за всеки обръщане дали в цикъл за или в докато цикъл.

Ако установим, че сумата от два елемента е равна на третия елемент, ще отпечатаме тези три елемента масив, те могат да образуват AP. Ще актуализираме стойността на j и k според нашия алгоритъм. Ако намерим сумата от два елемента по-малка от два пъти от третия елемент. Ще увеличим стойността на k, или ако намерим сумата, по-голяма от два пъти от третия елемент, ще намалим стойността на j. Това ще продължи, докато не преминем целия масив и открием всички възможни елементи, които могат да образуват AP.

код

C ++ код за отпечатване на всички тризнаци в сортиран масив, които образуват AP

#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

Java код за отпечатване на всички триплети в сортиран масив, които образуват AP

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

Анализ на сложността

Сложност във времето

На2където "н"  е броят на елементите в масива. Тъй като имаме два вложени цикъла, където първият цикъл работи, докато стигнем до края и след това вторият вложен цикъл се използва за намиране на елементите на AP.

Сложност на пространството

O (1) тъй като не се изисква допълнително пространство.