მასივის შეცვლა ისე, რომ arr [i]> = arr [j] თუ i არის ლუწი და arr [i] <= arr [j] თუ i უცნაურია და j <i


Რთული ტური საშუალო
ხშირად ეკითხებიან Accenture Adobe Amazon ფაქტები Zoho
Array

დავუშვათ, რომ მთელი რიცხვი გაქვთ მასივი. პრობლემის დებულება ითხოვს მასივის გადაჯგუფებას ისე, რომ მასივში ლუწი პოზიციის ელემენტები უნდა აღემატებოდეს მასზე არსებულ ყველა ელემენტს, ხოლო უცნაურ პოზიციებზე ნაკლები უნდა იყოს ელემენტები წინა ელემენტებზე.

მაგალითი

შეყვანის

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

გამოყვანის

4 6 4 8 2 9 1

განმარტება

ლუწი პოზიციების ყველა ელემენტი უფრო მეტია ვიდრე ყველა ელემენტი მის წინაშე და უცნაურ პოზიციებზე ნაკლებია წინა ელემენტებზე.

ალგორითმი

  1. დააყენეთ evenP პოზიცია n / 2-ზე.
  2. დააყენეთ oddPosition n - evenPosition.
  3. შექმნა მასივი (დროებითი).
  4. შეინახეთ მოცემული მასივის ყველა ელემენტი ამ დროებით მასივში.
  5. დროებითი მასივის დალაგება.
  6. დააყენეთ j ტოლია უცნაური პოზიციის -1.
  7. გადაწერეთ დროებითი ორიგინალი მასივი [j] მოცემული მასივის თანაბარ პოზიციაზე (ინდექსაციის საფუძველზე) და შეამცირეთ j- ის მნიშვნელობა 1-ით
  8. დააყენეთ j oddPosition- ზე.
  9. გადაწერეთ დროებითი ორიგინალი მასივიდან [j] მოცემული მასივის უცნაურ პოზიციაზე (ინდექსაციის საფუძველზე) და გაზარდეთ j- ის მნიშვნელობა 1-ით.
  10. დაბეჭდეთ ორიგინალი მასივი, რადგან განახლება ხდება ორიგინალ მასივში.

განმარტება

მთელი რიცხვების მასივის გათვალისწინებით, ჩვენი ამოცანაა, მასივი გადავალაგოთ ისე, რომ ელემენტები ლუწი რაოდენობისას უფრო მეტი იყოს, ვიდრე ყველა ელემენტი. და პოზიციების უცნაური რაოდენობის ელემენტები უნდა იყოს ნაკლები, ვიდრე მასზე არსებული ყველა რიცხვი. მაგალითში შეგვიძლია დავინახოთ, რომ ლუწი პოზიციების ელემენტები უფრო მეტია ვიდრე ყველა მის წინა რიცხვი. აქ ჩვენ არ მივიღებთ მას ინდექსზე დაფუძნებულ ნუმერაციად. 0 პოზიციაზე ელემენტი უნდა განიხილებოდეს, როგორც უცნაური 1 პოზიცია. 1st მასივის პოზიცია არის 2 პოზიცია, რომელიც არის ლუწი, აქ ჩვენ არ განვიხილავთ მასიზე დაფუძნებულ ინდექსს ჩვენს შედეგში, ჩვენ ვიწყებთ 1-დან უცნაურად n რიცხვამდე.

გააკეთეთ ორიგინალი მასივის ასლი დროებით მასივში, დათვალეთ რამდენი ლუწი და უცნაური პოზიცია შეიძლება იყოს მოცემულ მასივში. შემდეგ, ჩვენ ვაპირებთ დავალაგოთ მასივი მზარდი თანმიმდევრობით. ახლა განაახლეთ მასივის ელემენტები უცნაურ პოზიციაზე (არა მასივზე დაფუძნებული ინდექსაცია), დროებითი მასივიდან, როგორც oddPosition- ის შემცირებული მნიშვნელობები - 1-დან 0-მდე.

დროებითი მასივის ნახევარიდან ყველა ელემენტი შენახული იქნება თავდაპირველი მასივის უცნაურ მდგომარეობაში. ანალოგიურად, ჩვენ ვინახავთ დროებითი მასივის მეორე ნახევრის დანარჩენი მნიშვნელობების შენახვას ორიგინალი მასივის თანაბარ მდგომარეობაში, ამ წესით შეგვიძლია განვალაგოთ მასივი ისე, რომ ელემენტები უფრო მეტ პოზიციებზე და უცნაური ელემენტები. პოზიციები უცნაურ ელემენტებზე იქნება უფრო მცირე ვიდრე ყველა ელემენტი, ვიდრე ეს შესაბამისად იქნება.

მასივის შეცვლა ისე, რომ 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

ჯავა პროგრამა

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 log n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n)  სადაც "ნ"  არის მასივის ელემენტების რაოდენობა.