പരമാവധി മിനിമം ഫോമിൽ അറേ നൽകിയ പുന range ക്രമീകരണം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ക്യാപിറ്റൽ വൺ സിസ്കോ ഫേസ്ബുക്ക് ഗൂഗിൾ മോർഗൻ സ്റ്റാൻലി ഒറാക്കിൾ വിഎംവെയർ
അറേ

പ്രശ്നം പ്രസ്താവന

“പരമാവധി മിനിമം ഫോമിൽ നൽകിയ ശ്രേണി പുന ar ക്രമീകരിക്കുക” പ്രശ്‌നത്തിൽ, ഞങ്ങൾ ഒരു അടുക്കിയിരിക്കുന്നു ശ്രേണി N ഘടകങ്ങൾ അടങ്ങിയിരിക്കുന്നു. ഇതര ഘടകങ്ങൾ ith max, ith min എന്നിങ്ങനെ നൽകിയിരിക്കുന്ന പോസിറ്റീവ് സംഖ്യകളുടെ അടുക്കിയ ശ്രേണി പുന range ക്രമീകരിക്കുക. മൂലകങ്ങളുടെ പുന ar ക്രമീകരണത്തെക്കുറിച്ച് നന്നായി മനസ്സിലാക്കുന്നതിന് ചുവടെ കാണുക-

അറേ [0] = അറേയുടെ പരമാവധി മൂല്യം, അറേ [1] = അറേയുടെ ഏറ്റവും കുറഞ്ഞ മൂല്യം, അറേ [2] = അറേയുടെ രണ്ടാമത്തെ പരമാവധി മൂല്യം, അറേ [3] = അറേയുടെ രണ്ടാമത്തെ മിനിമം മൂല്യം, അറേ [4] = അറേയുടെ മൂന്നാമത്തെ പരമാവധി മൂല്യം …… തുടങ്ങിയവ.

ഉദാഹരണം

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

അൽഗോരിതം

  1. പരിഷ്‌ക്കരിച്ച അറേ സംഭരിക്കുന്നതിന് ഒരു സഹായ ഡമ്മി അറേ സൃഷ്‌ടിക്കുക.
  2. അറേയുടെ കോർണർ സൂചികകളായി താഴ്ന്നതും ഉയർന്നതുമായ സമാരംഭിക്കുക.
  3. ഇതര മാക്സും മിനിറ്റും പകർത്താൻ ഒരു വേരിയബിൾ എക്സ് സംഭരിച്ച് ട്രൂ സമാരംഭിക്കുക.
  4. എക്സ് = ട്രൂ ആണെങ്കിൽ ഞങ്ങൾ പരമാവധി മൂല്യം പകർത്തുന്നു, എക്സ് = ഫാൾസ് ആണെങ്കിൽ ഞങ്ങൾ മിനി മൂല്യം പകർത്തുന്നു.
  5. സഹായ അറേയിലേക്ക് ഘടകങ്ങൾ പകർത്താൻ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക. പുതിയ അറേയിലേക്ക് ഒരു ഘടകം പകർത്തിയ ശേഷം എക്‌സിന്റെ മൂല്യം വിപരീതമാക്കുക.
  6. എക്സ് അവസാനം മുതൽ ട്രൂ കോപ്പി ഘടകമാണെങ്കിൽ, എക്സ് മുന്നിൽ നിന്ന് തെറ്റായ പകർപ്പ് ഘടകമാണെങ്കിൽ മുന്നോട്ട് നീങ്ങുന്നു.
  7. തന്നിരിക്കുന്ന അറേയിലേക്ക് സഹായ അറേ പകർത്തുക.
  8. അറേ പ്രിന്റുചെയ്യുക, ഘടകങ്ങൾ പുന ran ക്രമീകരിക്കും.

നടപ്പിലാക്കൽ

പുനർ‌ക്രമീകരണത്തിനായുള്ള സി ++ പ്രോഗ്രാം പരമാവധി മിനിമം ഫോമിൽ നൽകിയിട്ടുള്ള അറേ

#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

പുന range ക്രമീകരണത്തിനായുള്ള ജാവ പ്രോഗ്രാം പരമാവധി മിനിമം ഫോമിൽ നൽകിയിട്ടുള്ള അറേ

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഇവിടെ ഞങ്ങൾ രണ്ട് പോയിന്റർ രീതികൾ ഉപയോഗിക്കുന്നു, അവ പരമാവധി n തവണ പ്രവർത്തിക്കുന്നു. അതിനാൽ, ഈ സാഹചര്യത്തിൽ സമയ സങ്കീർണ്ണത രേഖീയമാണെന്ന് നമുക്ക് പറയാൻ കഴിയും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) കാരണം മൂലകങ്ങളെ പരമാവധി മൂലകത്തിന്റെയും കുറഞ്ഞ മൂലകത്തിന്റെയും രൂപത്തിൽ സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു സഹായ അറേ ഉപയോഗിക്കുന്നു.

അവലംബം