Verilən Arrayı Maksimum Minimum Formada yenidən təşkil edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Bloomberg Capital One Cisco Facebook google Morgan Stanley Kahin VMware
GeyimBaxılıb 710

Problem bəyanat

“Maksimum Minimum Formada Verilən Arrayın Yenidən Düzəldilməsi” problemində bir sıra verdik array tərkibində N elementi var. Alternativ elementlər ith max və ith min olsun deyə verilən sıralanmış müsbət tam ədədi yenidən düzəldin. Elementlərin yenidən düzəldilməsini daha yaxşı başa düşmək üçün aşağıya baxın -

Array [0] = massivin maksimum dəyəri, Array [1] = serialın minimum dəyəri, Array [2] = arrayın ikinci maksimum dəyəri, Array [3] = arrayın ikinci minimum dəyəri, Array [4] = Dizinin 3-cü maksimum dəyəri ....... və s.

misal

7
1 2 3 4 5 6 7
7 1 6 2 5 3 4

Alqoritm

  1. Dəyişdirilmiş massivi saxlamaq üçün köməkçi saxta bir sıra yaradın.
  2. Dizinin künc göstəriciləri kimi aşağı və yüksək başlanğıc.
  3. Alternativ max və min kopyalamaq üçün bir dəyişən X saxla və True başladın.
  4. X = True olduqda maksimum, X = False isə min dəyəri kopyalayırıq.
  5. Elementləri köməkçi massivə kopyalamaq üçün döngə işlədin. Bir elementi yeni massivə kopyaladıqdan sonra X-nin dəyərini tərsinə çevirin.
  6. X doğru kopyalama elementidirsə və geriyə doğru hərəkət edərsə X yalnış kopyalama elementidir və irəli hərəkət edir.
  7. Köməkçi massivi verilmiş massivə kopyalayın.
  8. Dizini çap edin, elementlər yenidən düzəldiləcək.

Həyata keçirilməsi

Maksimum Minimum Formada verilmiş Dizini Yenidən Düzəltmək üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
 
//function to rearrange the given sorted array in maximum minimum form
void RearrangeMaxMin(int array[], int N)
{
    int temp[N];//auxilary dummy array with all zeroes
    for (int i=0; i<N; i++)
       {
           temp[i] = 0;
       }
    int low=0, high=N-1; // corner indices of the array 
    int X = true; // indication for which element should be copied
    //copying elements into the temp array
    //according to the given condition
    for (int i=0; i<N; i++)
    {
        if(X)
            {
                temp[i] = array[high--];
            }
        else
            {
                temp[i] = array[low++];
            }
        X = !X;
    }
    for (int i=0; i<N; i++)
     {
        array[i] = temp[i];
     }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout << array[i] << " ";
       }
}
// main function
int main()
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "Input array\n";
    PrintArray(array,N);
    RearrangeMaxMin(array,N);
    cout << "\nOutput array\n";
    PrintArray(array,N);
    return 0;
}
Input array
1 2 3 4 5 6 7 8 9 
Output array
9 1 8 2 7 3 6 4 5

Maksimum Minimum Formada Verilmiş Dizini Yenidən Düzəltmək üçün Java Proqramı

import java.util.Scanner;
class sum
{
    //function to rearrange the given sorted array in maximum minimum form
    public static void RearrangeMaxMin(int array[], int N)
    {
        int temp[] = new int [N];//auxilary dummy array with all zeroes
        for (int i=0; i<N; i++)
           {
               temp[i] = 0;
           }
        int low=0, high=N-1; // corner indices of the array 
        int X = 1; // indication for which element should be copied
        //copying elements into the temp array
        //according to the given condition
        for (int i=0; i<N; i++)
        {
            if(X==1)
                {
                    temp[i] = array[high--];
                }
            else
                {
                    temp[i] = array[low++];
                }
            if(X==1)
            {
                X=0;
            }
            else
            {
                X=1;
            }
        }
        for (int i=0; i<N; i++)
         {
            array[i] = temp[i];
         }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Input array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        RearrangeMaxMin(a,n);
        System.out.println("Output array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}
5
5 4 3 2 1
Input array
5 4 3 2 1 
Output array
1 5 2 4 3

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada n - verilən massivdə mövcud olan elementlərin sayı. Burada ən çox n dəfə işləyən iki göstərici metodundan istifadə edirik. Beləliklə, bu vəziyyətdə zaman mürəkkəbliyinin xətti olduğunu deyə bilərik.

Kosmik Mürəkkəblik

O (N) çünki elementləri maksimum element və minimum element şəklində saxlamaq üçün köməkçi bir sıra istifadə edirik.

References

Translate »