დაბეჭდეთ ყველა სამეული სამი დახარისხებული მასივით, რომელიც ქმნის AP- ს


Რთული ტური საშუალო
ხშირად ეკითხებიან Accenture თანამოსაყრელი კადენს ინდოეთი Google ინფოეჯი Intuit Pinterest
Array Hash Searching

პრობლემა "ყველა სამმაგი ბეჭდვა დახარისხებული მასივიდან, რომლებიც ქმნიან 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 && კ <ნ.
    1. შეამოწმეთ, არის თუ არა მასივის ორი მიმდინარე ელემენტის ჯამი ტოლი სხვა მასივის ელემენტის ორჯერ,
      1. თუ სიმართლეა, ამობეჭდეთ მიმდინარე სამი ელემენტი და შეამცირეთ და გაზრდით k და j მნიშვნელობას.
    2. შეამოწმეთ, არის თუ არა ორი ელემენტის ჯამი ორჯერ ნაკლები სხვა ელემენტისა, შემდეგ, k გაზრდით 1-ით.
    3. შეამოწმეთ, ორი ელემენტის ჯამი მეტია თუ არა სხვა ელემენტის ორჯერ, შემდეგ, j შემცირება 1-ით.

განმარტება

ჩვენ მივეცით ა დალაგებულია მასივი. ჩვენ გვთხოვენ გავერკვიოთ ყველა ის სამეული, რომლებსაც შეუძლიათ შექმნან არითმეტიკული პროგრესი. არითმეტიკული პროგრესიით შეიძლება განისაზღვროს როგორც რიცხვითი თანმიმდევრობა, რომელშიც ყველა ელემენტი მოდის თანმიმდევრულად მათ შორის განსაკუთრებული მანძილით მთლიანი თანმიმდევრობით. სამივეს ვიპოვით AP- ის ფორმულით, რომელშიც ნათქვამია a + c = 2b, ეს არის თუ ორი რიცხვის ჯამი ტოლია მესამე რიცხვის ორჯერ.

მთელი მასივის გადაკვეთა ერთით მარყუჟისთვის და ა ხოლო მარყუჟი, 'while loop' აპირებს შეამოწმოს, აღმოვაჩენთ თუ არა, რომ სამივე ელემენტს შეუძლია შექმნას AP ან არა. ჩვენ დავაყენებთ j მნიშვნელობას ერთით ნაკლები ვიდრე i და k მნიშვნელობას ერთზე მეტს ვიდრე i მნიშვნელობას, როდესაც ჩვენ გადავკვეთთ for 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

ჯავის კოდი, რომ დალაგდეს ყველა სამეული სამი დახარისხებული მასივიდან, რომელიც ქმნის 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) რადგან დამატებითი ადგილი არ არის საჭირო.