Arանգվածը վերադասավորեք այնպես, որ arr [i]> = arr [j] եթե i է զույգ, և arr [i] <= arr [j] եթե i կենտ է, և j <i


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Accenture Adobe Amazon Փաստեր Zoho
Դասավորություն

Ենթադրենք, որ դուք ունեք ամբողջ թիվ դասավորություն, Խնդրի հայտարարությունը խնդրում է զանգվածը վերադասավորել այնպես, որ զանգվածի զույգ դիրքի տարրերը լինեն ավելի մեծ, քան իրենից առաջ գտնվող բոլոր տարրերը, իսկ տարօրինակ դիրքերում գտնվող տարրերը պետք է պակաս լինեն նախորդներից:

Օրինակ

Մուտքային

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

Արտադրողականություն

4 6 4 8 2 9 1

բացատրություն

Evenույգ դիրքի բոլոր տարրերն ավելի մեծ են, քան իրենից առաջ գտնվող բոլոր տարրերը, իսկ կենտ դիրքերում գտնվող տարրերն ավելի քիչ են, քան նախորդ տարրերը:

Ալգորիթմ

  1. Սահմանեք evenPosition- ը n / 2:
  2. Սահմանել oddPosition- ը n - evenPosition:
  3. Ստեղծեք զանգված (ժամանակավոր):
  4. Տրված զանգվածի բոլոր տարրերը պահեք այս ժամանակավոր զանգվածում:
  5. Տեսակավորել ժամանակավոր զանգվածը:
  6. Սահմանել j հավասար oddPosition -1:
  7. Պատճենել ժամանակավորից սկզբնական զանգվածը [j] տրված զանգվածի հավասար դիրքում (ինդեքսավորման հիման վրա) և j- ի արժեքը 1-ով նվազեցնել:
  8. Սահմանեք j- ը oddPosition- ում:
  9. Պատճենել ժամանակավորը սկզբնական զանգվածին [j] տվյալ զանգվածի կենտ դիրքում (ինդեքսավորման հիման վրա) և j- ի արժեքն ավելացնել 1-ով:
  10. Տպեք բնօրինակ զանգվածը, քանի որ թարմացումը կատարվում է բնօրինակ զանգվածում:

բացատրություն

Հաշվի առնելով ամբողջ թվերի զանգվածը, մեր խնդիրն է զանգվածը վերադասավորել այնպես, որ հավասար դիրքերում գտնվող տարրերը լինեն ավելի մեծ, քան իրենից առաջ գտնվող բոլոր տարրերը: Եվ դիրքերի կենտ քանակի տարրերը պետք է պակաս լինեն, քան դրան նախորդող բոլոր թվերը: Մենք օրինակում կարող ենք տեսնել, որ զույգ դիրքերում գտնվող տարրերն ավելի մեծ են, քան իրեն նախորդող բոլոր թվերը: Այստեղ մենք դա չենք ընդունում որպես ինդեքսի վրա հիմնված համարակալում: 0 դիրքի տարրը պետք է դիտվի որպես 1 դիրքորոշում, որը տարօրինակ է: 1st զանգվածի դիրքը 2 դիրք է, որը զույգ է, այստեղ մենք արդյունքի վրա հիմնված ինդեքսավորումը չենք դիտարկում, մենք 1-ից սկսում ենք որպես տարօրինակից n թվեր:

Կազմեք բնօրինակ զանգվածի կրկնօրինակը ժամանակավոր զանգվածում, հաշվեք, թե քանի զույգ և կենտ դիրքեր կարող են լինել տվյալ զանգվածում: Այնուհետև, մենք պատրաստվում ենք զանգվածը տեսակավորել աճող կարգով: Այժմ թարմացրեք զանգվածի տարրերը կենտ դիրքում (ոչ զանգվածի վրա հիմնված ինդեքսավորում), ժամանակավոր զանգվածից որպես oddPosition- ի նվազող արժեքներ `1-ից 0:

Temporaryամանակավոր զանգվածի կեսից ստացված բոլոր տարրերը կպահվեն սկզբնական զանգվածի կենտ դիրքում: Նմանապես, մենք պահելու ենք, որ ժամանակավոր զանգվածի երկրորդ կեսի մնացած արժեքները կպահպանվեն սկզբնական զանգվածի հավասար դիրքում, այս եղանակով մենք կարող ենք զանգվածը վերադասավորել այնպես, որ տարրերն ավելի մեծ դիրքերում և տարրերը տարօրինակ լինեն: տարօրինակ տարրերի դիրքերը համապատասխանաբար փոքր կլինեն, քան դրան նախորդող բոլոր տարրերը:

Arանգվածը վերադասավորեք այնպես, որ arr [i]> = arr [j] եթե i է զույգ, և arr [i] <= arr [j] եթե i կենտ է, և j <i

Իրականացման

C ++ ծրագիր

#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

Java ծրագիր

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n տեղեկամատյան n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n)  որտեղ «Ն»  զանգվածում տարրերի քանակն է: