סידור מחדש של מערך כך ש arr [i]> = arr [j] אם i הוא שווה ו arr [i] <= arr [j] אם i הוא מוזר ו- j <i


רמת קושי בינוני
נשאל לעתים קרובות אקסנצ'ר Adobe אמזון בעברית סט עובדות Zoho
מערך

נניח שיש לך מספר שלם מערך. הצהרת הבעיה מבקשת לסדר מחדש את המערך באופן שהאלמנטים במיקום שווה במערך צריכים להיות גדולים יותר מכל האלמנטים שלפניו והאלמנטים במיקומים מוזרים צריכים להיות פחות מהאלמנטים שלפניו.

דוגמה

קֶלֶט

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

תְפוּקָה

4 6 4 8 2 9 1

הסבר

כל האלמנטים במיקומים שווים גדולים יותר מכל האלמנטים שלפניו והאלמנטים במיקומים מוזרים הם פחות מהאלמנטים הקודמים.

אַלגוֹרִיתְם

  1. הגדר את המיקום אפילו ל- 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 כאל מיקום אחד שאינו מוזר. 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

תוכנית 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

ניתוח מורכבות

מורכבות זמן

O (n יומן n) איפה "N" הוא מספר האלמנטים במערך.

מורכבות בחלל

O (n)  איפה "N"  הוא מספר האלמנטים במערך.