అర్రే [i]> = arr [j] నేను సమానంగా ఉంటే అర్రే [i] <= arr [j] నేను బేసి మరియు j <i


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది యాక్సెంచర్ Adobe అమెజాన్ ఫాక్ట్‌సెట్ జోహో
అర్రే

మీకు పూర్ణాంకం ఉందని అనుకుందాం అమరిక. సమస్యా ప్రకటన శ్రేణిని సరిదిద్దడానికి అడుగుతుంది, తద్వారా శ్రేణిలో సమాన స్థానం వద్ద ఉన్న మూలకాలు దాని ముందు ఉన్న అన్ని మూలకాల కంటే ఎక్కువగా ఉండాలి మరియు బేసి స్థానాల్లోని మూలకాలు దాని ముందు ఉన్న మూలకాల కంటే తక్కువగా ఉండాలి.

ఉదాహరణ

ఇన్పుట్

arr [] = {1, 4, 6, 2, 4, 8, 9}

అవుట్పుట్

4 6 4 XIX 8 2 9

వివరణ

సమాన స్థానాల్లోని అన్ని అంశాలు దాని ముందు ఉన్న అన్ని మూలకాల కంటే ఎక్కువగా ఉంటాయి మరియు బేసి స్థానాల్లోని మూలకాలు మునుపటి మూలకాల కంటే తక్కువగా ఉంటాయి.

అల్గారిథం

  1. సరి స్థానం n / 2 కు సెట్ చేయండి.
  2. బేసి పొజిషన్‌ను n - evenPosition కు సెట్ చేయండి.
  3. శ్రేణిని సృష్టించండి (తాత్కాలికం).
  4. ఇచ్చిన శ్రేణిలోని అన్ని అంశాలను ఈ తాత్కాలిక శ్రేణిలో నిల్వ చేయండి.
  5. తాత్కాలిక శ్రేణిని క్రమబద్ధీకరించండి.
  6. J ను బేసి స్థానం -1 కు సమానం.
  7. ఇచ్చిన శ్రేణి యొక్క సమాన స్థానం (ఇండెక్సింగ్ ఆధారిత) వద్ద తాత్కాలిక నుండి అసలు శ్రేణి [j] కు కాపీ చేసి, j యొక్క విలువను 1 తగ్గించండి.
  8. J ని బేసి స్థానానికి సెట్ చేయండి.
  9. ఇచ్చిన శ్రేణి యొక్క బేసి స్థానం (ఇండెక్సింగ్ ఆధారిత) వద్ద తాత్కాలిక అసలు శ్రేణి [j] కు కాపీ చేసి, j యొక్క విలువను 1 పెంచండి.
  10. అసలు శ్రేణిలో నవీకరణ చేయబడినందున అసలు శ్రేణిని ముద్రించండి.

వివరణ

పూర్ణాంకాల శ్రేణిని బట్టి, శ్రేణిని క్రమాన్ని మార్చడం మా స్థానం, దాని సంఖ్యల సంఖ్య వద్ద ఉన్న మూలకాలు దాని ముందు ఉన్న అన్ని మూలకాల కంటే ఎక్కువగా ఉండాలి. మరియు బేసి సంఖ్య స్థానాల్లోని మూలకాలు దాని ముందు ఉన్న అన్ని సంఖ్యల కంటే తక్కువగా ఉండాలి. సమాన స్థానాల్లోని మూలకాలు దాని ముందు ఉన్న అన్ని సంఖ్యల కంటే ఎక్కువగా ఉన్నందున మనం ఉదాహరణలో చూడవచ్చు. ఇక్కడ మేము దీనిని ఇండెక్స్-బేస్డ్ నంబరింగ్ గా తీసుకోవడం లేదు. 0 స్థానాల్లోని మూలకాన్ని బేసి 1 స్థానంగా పరిగణించాలి. 1st శ్రేణి యొక్క స్థానం 2 స్థానం, అంటే ఇక్కడ మన ఫలితంలో శ్రేణి-ఆధారిత సూచికను పరిగణించటం లేదు, మేము 1 నుండి బేసిగా n సంఖ్యలకు ప్రారంభిస్తాము.

అసలు శ్రేణి యొక్క కాపీని తాత్కాలిక శ్రేణిలోకి తయారు చేయండి, ఇచ్చిన శ్రేణిలో ఎన్ని సరి మరియు బేసి స్థానాలు ఉండవచ్చో లెక్కించండి. అప్పుడు, మేము శ్రేణిని క్రమంలో క్రమబద్ధీకరించబోతున్నాము. ఇప్పుడు శ్రేణి యొక్క మూలకాలను బేసి స్థానంలో (నాన్-అర్రే బేస్డ్ ఇండెక్సింగ్), తాత్కాలిక శ్రేణి నుండి బేసి స్థానం - 1 నుండి 0 వరకు విలువలను తగ్గించండి.

తాత్కాలిక శ్రేణిలో సగం నుండి మూలకాలన్నీ అసలు శ్రేణి యొక్క బేసి స్థానంలో నిల్వ చేయబడతాయి. అదేవిధంగా, తాత్కాలిక శ్రేణి యొక్క రెండవ సగం యొక్క మిగిలిన విలువలను అసలు శ్రేణి యొక్క సమాన స్థానం వద్ద నిల్వ చేస్తాము, ఈ పద్ధతిలో, మేము శ్రేణిని క్రమాన్ని మార్చవచ్చు, తద్వారా మూలకాలు ఎక్కువ స్థానాల్లో మరియు బేసి వద్ద మూలకాలు బేసి మూలకాల వద్ద ఉన్న స్థానాలు దాని ముందు ఉన్న అన్ని మూలకాల కంటే చిన్నవిగా ఉంటాయి.

అర్రే [i]> = arr [j] నేను సమానంగా ఉంటే అర్రే [i] <= arr [j] నేను బేసి మరియు j <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 లాగ్ n)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N”  శ్రేణిలోని మూలకాల సంఖ్య.