Барлық үштіктерді сұрыпталған массивке басып шығарыңыз, олар AP құрайды  


Күрделілік дәрежесі орта
Жиі кіреді Accenture Акколит Cadence Үндістан Google InfoEdge Intuit Pinterest
Array Hash іздеу

«Барлық үштіктерді 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-ге азайтыңыз.

Түсіндіру

Біз а сұрыпталған массив. Бізден арифметикалық прогрессия құра алатын барлық үшемді анықтауды сұрайды. Арифметикалық прогрессияны барлық элементтер бірізділікпен бүкіл тізбек бойымен олардың арасындағы белгілі бір қашықтыққа келетін сандық тізбек деп анықтауға болады. Біз үштікті AP формуласы бойынша табамыз, онда a + c = 2b, егер екі санның қосындысы үшінші санның екі есесіне тең болса.

Сондай-ақ, қараңыз
Біртіндеп оң нәтиже алу үшін минималды мән Leetcode шешімі

Барлық массивті цикл үшін және а while цикл, 'while цикл' элементтердің үшеуі AP құра алатынын немесе болмайтынын тексереді. Біз for циклі арқылы өткен сайын j-тің мәнін i-ден кемге, ал k -дың мәнін i-ден бірге артық етіп қоямыз. Ол біз үшін тексеретін элементті алады, сондықтан бізде [i], arr [j] және arr [k] тексеретін үш элемент болған сайын, әрқайсысы үшін өзгеретін i, j және k мәні болады in for loop немесе in түрінде жүру while цикл.

Егер біз екі элементтің қосындысын үшінші элементке тең деп тапсақ, онда массивтің үш элементін шығарамыз, олар AP құра алады. J және k мәндерін алгоритмімізге сәйкес жаңартамыз. Егер біз үшінші элементтен екі еседен кем екі элементтің қосындысын тапсақ. K-дің мәнін көбейтеміз немесе үшінші элементтің екі еселенген қосындысын тапсақ, j-нің мәнін төмендетеміз. Бұл біз бүкіл массивті айналып өтіп, AP құра алатын барлық мүмкін элементтерді анықтағанға дейін жалғасады.

код  

С ++ коды, барлық үштіктерді 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-ді құрайтын сұрыпталған жиымға басып шығаруға арналған 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

Күрделілікті талдау  

Уақыттың күрделілігі

O (n2қайда «N»  - бұл массивтегі элементтер саны. Өйткені бізде екі кірістірілген цикл бар, онда бірінші цикл біз аяқталғанға дейін жұмыс істейді, содан кейін екінші кірістірілген цикл AP элементтерін табу үшін қолданылады.

Сондай-ақ, қараңыз
Ішкі массивтің максималды мөлшері k-ге тең

Ғарыштың күрделілігі

O (1) өйткені қосымша орын қажет емес.