অ্যারেটিকে পুনরায় সাজান [i]> = আরআর [জে] যদি আমি সমানও হয় এবং আমিও [i] <= আরআর [জে] আমি বিজোড় এবং জে <i


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় Accenture রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ফ্যাক্সেট Zoho
বিন্যাস

মনে করুন আপনার একটি পূর্ণসংখ্যা রয়েছে বিন্যাস। সমস্যা বিবৃতি অ্যারেটিকে এমনভাবে পুনর্বিন্যস্ত করতে বলে যাতে অ্যারেতে সম অবস্থানের উপাদানগুলি তার আগে থাকা সমস্ত উপাদানের চেয়ে বেশি হওয়া এবং বিজোড় অবস্থানগুলিতে থাকা উপাদানগুলি এর আগে থাকা উপাদানের চেয়ে কম হওয়া উচিত।

উদাহরণ

ইনপুট

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

আউটপুট

4 6 4 8 2 9 1

ব্যাখ্যা

সম অবস্থানের সমস্ত উপাদান এর আগে থাকা সমস্ত উপাদানের চেয়ে বৃহত্তর এবং বিজোড় অবস্থানের উপাদানগুলি পূর্ববর্তী উপাদানগুলির চেয়ে কম থাকে।

অ্যালগরিদম

  1. এমনকি পজিশনটিকে এন / 2 তে সেট করুন।
  2. অডপজিশনটি n - এমনকি পজিশনে সেট করুন।
  3. একটি অ্যারে (অস্থায়ী) তৈরি করুন।
  4. প্রদত্ত অ্যারের সমস্ত উপাদান এই অস্থায়ী অ্যারেতে সঞ্চয় করুন।
  5. অস্থায়ী অ্যারে বাছাই করুন।
  6. বিজোড় অবস্থান -1 সমান জে সেট করুন।
  7. প্রদত্ত অ্যারের সমান অবস্থানে (সূচক ভিত্তিক) অস্থায়ী অনুলিপি করুন [জে] এবং জেটির মান 1 দ্বারা হ্রাস করুন।
  8. বিজোড় অবস্থানটি সেট করুন।
  9. প্রদত্ত অ্যারের বিজোড় অবস্থান (সূচী ভিত্তিক) এ অস্থায়ী অনুলিপি করুন [জে] এবং জ এর মান 1 দ্বারা বৃদ্ধি করুন।
  10. মূল অ্যারেতে আপডেটটি তৈরি হওয়ার কারণে মূল অ্যারেটি মুদ্রণ করুন in

ব্যাখ্যা

পূর্ণসংখ্যার একটি অ্যারে দেওয়া, আমাদের কাজটি অ্যারেটিকে এমনভাবে পুনর্বিন্যস্ত করা হচ্ছে যাতে সমান সংখ্যক পজিশনের উপাদানগুলি এর আগে থাকা সমস্ত উপাদানের চেয়ে বেশি হওয়া উচিত। এবং বিজোড় সংখ্যার অবস্থানের উপাদানগুলি এর আগে উপস্থিত সমস্ত সংখ্যার চেয়ে কম হওয়া উচিত। আমরা উদাহরণে দেখতে পাচ্ছি যে সম পজিশনে থাকা উপাদানগুলি এর আগে থাকা সমস্ত সংখ্যার চেয়ে বেশি। এখানে আমরা এটিকে সূচক ভিত্তিক নম্বর হিসাবে নিচ্ছি না। 0 পদের এলিমেন্টটিকে 1 পজিশনের সাথে বিজোড় হিসাবে বিবেচনা করা উচিত। ঘst একটি অ্যারের অবস্থান 2 পজিশন যা সমান, এখানে আমরা আমাদের ফলাফলটিতে অ্যারে-ভিত্তিক সূচীকরণ বিবেচনা করছি না, আমরা 1 থেকে বিজোড় হিসাবে শুরু করব start

অস্থায়ী অ্যারেতে মূল অ্যারের একটি অনুলিপি তৈরি করুন, একটি প্রদত্ত অ্যারেতে কতগুলি এমনকি বিজোড় অবস্থান হতে পারে তা গণনা করুন। তারপরে, আমরা ক্রমবর্ধমান ক্রমে বাছাই করতে যাচ্ছি। অरेজ উপাদানগুলি অদ্ভুত অবস্থানে (অ-অ্যারে ভিত্তিক সূচীকরণ) অদ্ভুত অবস্থান থেকে অস্থায়ী অ্যারে থেকে আপডেট করুন - 1 থেকে 0 values

অস্থায়ী অ্যারের অর্ধেক থেকে সমস্ত উপাদান মূল অ্যারের বিজোড় অবস্থানে সংরক্ষণ করা হবে। একইভাবে, আমরা অস্থায়ী অ্যারের দ্বিতীয়ার্ধের বাকি মানগুলি মূল অ্যারের সমপরিমাণে সংরক্ষণ করব, এই পদ্ধতিতে, আমরা অ্যারেটিকে পুনর্বিন্যাস করতে পারি যাতে উপাদানগুলি আরও বেশি অবস্থানে থাকে এবং উপাদানগুলি বিজোড়ভাবে হয় বিজোড় উপাদানগুলিতে অবস্থানগুলি যথাক্রমে এর আগে সমস্ত উপাদানের চেয়ে ছোট হবে।

অ্যারেটিকে পুনরায় সাজান [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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন লগ এন) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর)  কোথায় "এন"  অ্যারেতে উপাদানগুলির সংখ্যা।