Arrayı yenidən düzəldin ki, arr [i]> = arr [j] əgər i cüt olarsa və arr [i] <= arr [j] əgər i təkdirsə və j <i

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Tutaq ki, bir tam ədədin var array. Problem ifadəsi massivi yenidən düzəltməsini xahiş edir ki, massivdəki cüt mövqedəki elementlər ondan əvvəl bütün elementlərdən, tək mövqedəki elementlər əvvəlki elementlərdən az olmalıdır.

misal

Input

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

Buraxılış

4 6 4 8 2 9 1

Izahat

Cüt mövqedəki bütün elementlər ondan əvvəlki bütün elementlərdən daha böyükdür və tək vəziyyətdə olan elementlər əvvəlki elementlərdən azdır.

Alqoritm

1. EvenPosition n / 2 olaraq təyin edin.
2. OddPosition n - evenPosition olaraq təyin edin.
3. Bir sıra (müvəqqəti) yaradın.
4. Verilən massivin bütün elementlərini bu müvəqqəti massivdə saxlayın.
5. Müvəqqəti massivi çeşidləyin.
6. J-ni oddPosition -1-ə bərabər qoyun.
7. Müvəqqəti verilmiş massivin cüt mövqeyinə (indeksləşdirməyə əsaslanan) orijinal massivi [j] kopyalayın və j dəyərini 1-ə endirin.
8. J-ni oddPosition olaraq təyin edin.
9. Müvəqqəti verilmiş massivin tək vəziyyətdə (indeksləşdirməyə əsaslanan) orijinal massivə [j] kopyalayın və j dəyərini 1 artırın.
10. Yeniləmə orijinal massivdə edildiyi üçün orijinal seriyanı çap edin.

Izahat

Bir sıra tam ədədi nəzərə alsaq, vəzifəmiz massivi elə düzəltməkdir ki, cüt mövqedəki elementlər özündən əvvəlki bütün elementlərdən çox olsun. Və tək sayda mövqedəki elementlər ondan əvvəl mövcud olan bütün rəqəmlərdən az olmalıdır. Misalda cüt mövqedəki elementlərin əvvəlki rəqəmlərdən daha böyük olduğunu görə bilərik. Burada onu indeks əsaslı nömrələmə kimi qəbul etmirik. 0 mövqedəki element tək olan 1 mövqe kimi qəbul edilməlidir. 1^st bir sıra mövqeyi 2 mövqedir, hətta cütdür, nəticədə sıra əsaslı indeksləşdirməyi düşünmürük, 1-dən təkdən n-ə qədər başlayırıq.

Orijinal massivin surətini müvəqqəti massivə düzəldin, verilmiş massivdə neçə cüt və tək mövqe ola biləcəyini hesablayın. Ardından, serialı artan sırada sıralayacağıq. İndi sıra elementlərini tək mövqedə (sıra əsaslı olmayan indeksləşdirmə) müvəqqəti massivdən oddPosition - 1-dən 0-a qədər azalan dəyərlər kimi yeniləyin.

Müvəqqəti massivin yarısındakı bütün elementlər orijinal massivin tək vəziyyətdə saxlanacaqdır. Eynilə, müvəqqəti massivin ikinci yarısının dəyərlərinin qalan hissəsini orijinal massivin cüt mövqeyində saxlayacağıq, bu şəkildə ardıcıllıqla düzəldə bilərik ki, cüt mövqelərdəki elementlər daha çox və elementlər tək olsun. tək elementlərdəki mövqelər əvvəlcədən bütün elementlərdən kiçik olacaqdır.

Pin

Həyata keçirilməsi

C ++ proqramı

#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 proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n log n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n)  hara "N"  massivdəki elementlərin sayıdır.