അറേ പുന ar ക്രമീകരിക്കുക അത്തരത്തിലുള്ള [i]> = arr [j] ഞാൻ തുല്യമാണെങ്കിൽ അറ [i] <= arr [j] ഞാൻ വിചിത്രമാണെങ്കിൽ j <i


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് അഡോബി ആമസോൺ ഫാക്റ്റ്സെറ്റ് Zoho
അറേ

നിങ്ങൾക്ക് ഒരു സംഖ്യ ഉണ്ടെന്ന് കരുതുക ശ്രേണി. ഒരു അറേയിലെ ഇരട്ട സ്ഥാനത്തുള്ള ഘടകങ്ങൾ അതിനുമുമ്പുള്ള എല്ലാ ഘടകങ്ങളേക്കാളും വലുതും വിചിത്ര സ്ഥാനങ്ങളിലെ ഘടകങ്ങൾ അതിന് മുമ്പുള്ള ഘടകങ്ങളേക്കാൾ കുറവായിരിക്കുന്ന തരത്തിൽ അറേ പുന ar ക്രമീകരിക്കാൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

ഇൻപുട്ട്

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

ഔട്ട്പുട്ട്

4 6 4 8 2 9 1

വിശദീകരണം

ഇരട്ട സ്ഥാനങ്ങളിലെ എല്ലാ ഘടകങ്ങളും അതിനുമുമ്പുള്ള എല്ലാ ഘടകങ്ങളേക്കാളും വലുതാണ്, വിചിത്രമായ സ്ഥാനങ്ങളിലെ ഘടകങ്ങൾ മുമ്പത്തെ ഘടകങ്ങളേക്കാൾ കുറവാണ്.

അൽഗോരിതം

  1. ഇരട്ട സ്ഥാനം n / 2 ആയി സജ്ജമാക്കുക.
  2. വിചിത്രമായ സ്ഥാനം n - evenPosition ലേക്ക് സജ്ജമാക്കുക.
  3. ഒരു അറേ സൃഷ്ടിക്കുക (താൽക്കാലികം).
  4. തന്നിരിക്കുന്ന അറേയുടെ എല്ലാ ഘടകങ്ങളും ഈ താൽക്കാലിക അറേയിൽ സംഭരിക്കുക.
  5. താൽക്കാലിക അറേ അടുക്കുക.
  6. വിചിത്രമായ സ്ഥാനം -1 ന് തുല്യമായി j സജ്ജമാക്കുക.
  7. തന്നിരിക്കുന്ന അറേയുടെ ഇരട്ട സ്ഥാനത്ത് (ഇൻഡെക്സിംഗ് അടിസ്ഥാനമാക്കിയുള്ളത്) താൽക്കാലികത്തിലേക്ക് യഥാർത്ഥ അറേയിലേക്ക് പകർത്തുക, j യുടെ മൂല്യം 1 കുറയ്ക്കുക.
  8. വിചിത്രമായ സ്ഥാനത്തേക്ക് j സജ്ജമാക്കുക.
  9. തന്നിരിക്കുന്ന അറേയുടെ വിചിത്രമായ സ്ഥാനത്ത് (ഇൻഡെക്സിംഗ് അടിസ്ഥാനമാക്കിയുള്ള) താൽക്കാലികത്തെ യഥാർത്ഥ അറേയിലേക്ക് [j] പകർത്തുക, j യുടെ മൂല്യം 1 വർദ്ധിപ്പിക്കുക.
  10. യഥാർത്ഥ അറേയിൽ അപ്‌ഡേറ്റ് ചെയ്‌തിരിക്കുന്നതിനാൽ യഥാർത്ഥ അറേ പ്രിന്റുചെയ്യുക.

വിശദീകരണം

ഒരു കൂട്ടം സംഖ്യകൾ നൽകിയാൽ, സ്ഥാനങ്ങളുടെ ഇരട്ട സംഖ്യയിലുള്ള ഘടകങ്ങൾ അതിനുമുമ്പുള്ള എല്ലാ ഘടകങ്ങളേക്കാളും വലുതായിരിക്കേണ്ട രീതിയിൽ അറേ പുന ar ക്രമീകരിക്കുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. സ്ഥാനങ്ങളുടെ വിചിത്ര സംഖ്യയിലെ ഘടകങ്ങൾ അതിന് മുമ്പുള്ള എല്ലാ സംഖ്യകളേക്കാളും കുറവായിരിക്കണം. ഇരട്ട സ്ഥാനങ്ങളിലെ ഘടകങ്ങൾ അതിനുമുമ്പുള്ള എല്ലാ അക്കങ്ങളെക്കാളും വലുതായതിനാൽ നമുക്ക് ഉദാഹരണത്തിൽ കാണാൻ കഴിയും. ഇവിടെ ഞങ്ങൾ ഇത് സൂചിക അടിസ്ഥാനമാക്കിയുള്ള നമ്പറിംഗായി എടുക്കുന്നില്ല. 0 സ്ഥാനങ്ങളിലെ ഘടകത്തെ വിചിത്രമായ 1 സ്ഥാനമായി കണക്കാക്കണം. 1st ഒരു അറേയുടെ സ്ഥാനം 2 സ്ഥാനമാണ്, അതായത്, ഇവിടെ നമ്മുടെ ഫലത്തിൽ അറേ അടിസ്ഥാനമാക്കിയുള്ള സൂചികയിലല്ല ഞങ്ങൾ പരിഗണിക്കുന്നത്, ഞങ്ങൾ 1 മുതൽ ഒറ്റ സംഖ്യ വരെ n നമ്പറുകളായി ആരംഭിക്കുന്നു.

ഒറിജിനൽ അറേയുടെ ഒരു പകർപ്പ് താൽക്കാലിക അറേയിലേക്ക് നിർമ്മിക്കുക, തന്നിരിക്കുന്ന അറേയിൽ എത്ര ഇരട്ട സംഖ്യകൾ ഉണ്ടെന്ന് കണക്കാക്കുക. തുടർന്ന്, ഞങ്ങൾ ശ്രേണി ക്രമത്തിൽ അടുക്കാൻ പോകുന്നു. ഇപ്പോൾ അറേയിലെ ഘടകങ്ങൾ വിചിത്രമായ സ്ഥാനത്ത് (നോൺ-അറേ അധിഷ്ഠിത സൂചികയിലാക്കൽ) അപ്‌ഡേറ്റ് ചെയ്യുക, താൽക്കാലിക അറേയിൽ നിന്ന് വിചിത്ര സ്ഥാനത്തിന്റെ മൂല്യങ്ങൾ കുറയുന്നു - 1 മുതൽ 0 വരെ.

താൽക്കാലിക അറേയുടെ പകുതിയിൽ നിന്നുള്ള എല്ലാ ഘടകങ്ങളും യഥാർത്ഥ അറേയുടെ വിചിത്രമായ സ്ഥാനത്ത് സൂക്ഷിക്കും. അതുപോലെ, താൽക്കാലിക അറേയുടെ രണ്ടാം പകുതിയുടെ ബാക്കി മൂല്യങ്ങൾ ഞങ്ങൾ യഥാർത്ഥ അറേയുടെ ഇരട്ട സ്ഥാനത്ത് സൂക്ഷിക്കും, ഈ രീതിയിൽ, നമുക്ക് അറേ പുന ar ക്രമീകരിക്കാൻ കഴിയും, അതിലൂടെ മൂലകങ്ങൾ കൂടുതൽ സ്ഥാനത്തും മൂലകങ്ങൾ വിചിത്രമായും വിചിത്രമായ മൂലകങ്ങളിലെ സ്ഥാനങ്ങൾ അതിനുമുമ്പുള്ള എല്ലാ ഘടകങ്ങളേക്കാളും ചെറുതായിരിക്കും.

അറേ പുന ar ക്രമീകരിക്കുക അത്തരത്തിലുള്ള [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” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n)  എവിടെ “N”  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.