अ‍ॅरेची पुनर्रचना करा जसे की एर [i]> = अरर [जे] मी सम असल्यास आणि अर्र [i] <= अर [ज]] मी विचित्र असल्यास आणि जे <i


अडचण पातळी मध्यम
वारंवार विचारले ऐक्सचर अडोब ऍमेझॉन फॅक्टसेट Zoho
अरे

समजा तुमच्याकडे पूर्णांक असेल अॅरे. अडचणी स्टेटमेंट अ‍ॅरेची अशा प्रकारे रेंज ऑर्डर करण्यास सांगते की अ‍ॅरे मधील सम पोजीशनवरील घटक त्यापूर्वी असलेल्या सर्व घटकांपेक्षा जास्त असले पाहिजेत आणि विषम पोझिशन्सवरील घटक त्यापूर्वी असलेल्या घटकांपेक्षा कमी असावेत.

उदाहरण

इनपुट

अरे [] = {1, 4, 6, 2, 4, 8, 9}

उत्पादन

4 6 4 8 2 9 1

स्पष्टीकरण

सम स्थितीत असलेले सर्व घटक त्यापूर्वी असलेल्या सर्व घटकांपेक्षा मोठे असतात आणि विषम पदांवर असलेले घटक मागील घटकांपेक्षा कमी असतात.

अल्गोरिदम

  1. इव्हनपोजिशनला एन / 2 वर सेट करा.
  2. ऑडपोजिशनला एन - इव्हनपोजिशनवर सेट करा.
  3. अ‍ॅरे (तात्पुरते) तयार करा.
  4. दिलेल्या अ‍ॅरेचे सर्व घटक या तात्पुरते अ‍ॅरेमध्ये संचयित करा.
  5. तात्पुरते अ‍ॅरेची क्रमवारी लावा.
  6. ओडपोजिशन -१ च्या बरोबर j सेट करा.
  7. दिलेल्या अ‍ॅरेच्या सम स्थान (अनुक्रमणिका आधारित) वर तात्पुरते ते मूळ अ‍ॅरे [j] कॉपी करा आणि j चे मूल्य 1 ने कमी करा.
  8. ऑडपोजीशनवर j सेट करा.
  9. दिलेल्या अ‍ॅरेच्या विचित्र स्थितीवर (अनुक्रमणिका आधारित) अस्थायी कॉपी करा आणि j चे मूल्य 1 ने वाढवा.
  10. अद्ययावत मूळ अ‍ॅरेमध्ये केल्यापासून मूळ अ‍ॅरे मुद्रित करा.

स्पष्टीकरण

पूर्णांकांचा अ‍ॅरे दिल्यास, आमचे कार्य अशा प्रकारे अ‍रेची पुनर्रचना करणे आहे जेणेकरून समान पदांवर असलेले घटक त्यापूर्वी असलेल्या सर्व घटकांपेक्षा मोठे असावेत. आणि विचित्र संख्येच्या पोझिशन्सवरील घटक त्यापूर्वी असलेल्या सर्व आकडेवारीपेक्षा कमी असावेत. आम्ही उदाहरणात पाहू शकतो की सम स्थितीत असलेले घटक त्याच्या आधीच्या सर्व संख्येपेक्षा मोठे आहेत. येथे आम्ही अनुक्रमणिका-आधारित क्रमांकन म्हणून घेत नाही आहोत. 0 स्थानांवरील घटकांना 1 स्थान समजले पाहिजे जे विषम आहे. 1st अ‍ॅरेची स्थिती 2 स्थिती आहे जी सम आहे, येथे आम्ही आपल्या निकालामध्ये अ‍ॅरे-बेस्ड इंडेक्सिंगचा विचार करीत नाही, तर आपण 1 वरून एन नंबर पर्यंत सुरूवात करतो.

तात्पुरत्या अ‍ॅरेमध्ये मूळ अ‍ॅरेची एक प्रत बनवा, दिलेल्या अ‍ॅरेमध्ये किती समान आणि विचित्र स्थिती असू शकतात याची मोजणी करा. तर आपण वाढत्या क्रमाने अ‍ॅरे सॉर्ट करणार आहोत. आता अ‍ॅरेचे घटक विषम स्थितीवर (अ‍ॅरे-आधारित बेस्ड अनुक्रमणिका) अद्ययावत करा, तात्पुरते अ‍ॅरेपासून ऑडपोजिशन - 1 ते 0 चे मूल्य कमी होत आहेत.

अर्ध्या तात्पुरत्या अ‍ॅरेमधील सर्व घटक मूळ अ‍ॅरेच्या विचित्र स्थितीवर संग्रहित केले जातील. त्याचप्रमाणे आपण तात्पुरते अ‍ॅरेच्या दुसर्‍या अर्ध्याची उर्वरित व्हॅल्यूज मूळ अ‍ॅरेच्या समभागात संग्रहित केली जात आहोत. अशा प्रकारे आपण अ‍ॅरेची पुनर्रचना करू जेणेकरून सम स्थानांवरील घटक जास्त आणि विषम घटकांवर विलग होईल. विषम घटकांवरील स्थिती अनुक्रमे आधीच्या सर्व घटकांपेक्षा लहान असेल.

अ‍ॅरेची पुनर्रचना करा जसे की एर [i]> = अरर [जे] मी सम असल्यास आणि अर्र [i] <= अर [ज]] मी विचित्र असल्यास आणि जे <i

अंमलबजावणी

सी ++ प्रोग्राम

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeArrayEvenOdd(int arr[], int n)
{
    int evenPosition = n / 2;

    int oddPosition = n - evenPosition;

    int temporaryArray[n];

    for (int i = 0; i < n; i++)
        temporaryArray[i] = arr[i];

    sort(temporaryArray, temporaryArray + n);

    int j = oddPosition - 1;

    for (int i = 0; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j--;
    }

    j = oddPosition;

    for (int i = 1; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,4,6,2,4,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArrayEvenOdd(arr, n);
    printArray(arr,n);
    return 0;
}
4 6 4 8 2 9 1

जावा कार्यक्रम

import java.util.*;

class rearrangeArray
{
    public static void rearrangeArrayEvenOdd (int arr[], int n)
    {
        int evenPosition = n / 2;

        int oddPosition = n - evenPosition;

        int[] temporaryArray = new int [n];

        for (int i = 0; i < n; i++)
            temporaryArray[i] = arr[i];

        Arrays.sort(temporaryArray);
        int j = oddPosition - 1;

        for (int i = 0; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j--;
        }

        j = oddPosition;

        for (int i = 1; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j++;
        }
    }
    public static void printArray(int arr[], int n)
    {

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String argc[])
    {
        int[] arr = { 1,4,6,2,4,8,9};
        int size =arr.length;
        rearrangeArrayEvenOdd (arr, size);
        printArray(arr, size);

    }
}
4 6 4 8 2 9 1

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉग एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

O (n)  जेथे “एन”  अ‍ॅरे मधील घटकांची संख्या.