Αναδιάταξη της σειράς έτσι ώστε arr [i]> = arr [j] if i is even and arr [i] <= arr [j] if i is odd and j <i


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Accenture πλίθα αμαζόνα Γεγονότα 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 θέσεις πρέπει να αντιμετωπίζεται ως 1 θέση που είναι περίεργη. 1st Η θέση ενός πίνακα είναι 2 θέση που είναι ομοιόμορφη, εδώ δεν εξετάζουμε την ευρετηρίαση βάσει πίνακα στο αποτέλεσμα μας, ξεκινάμε από το 1 ως μονό έως n αριθμούς.

Δημιουργήστε ένα αντίγραφο του αρχικού πίνακα στον προσωρινό πίνακα, μετρήστε πόσες ζυγές και μονές θέσεις μπορούν να είναι σε έναν δεδομένο πίνακα. Στη συνέχεια, θα ταξινομήσουμε τον πίνακα σε αυξανόμενη σειρά. Τώρα ενημερώστε τα στοιχεία του πίνακα στη μονή θέση (ευρετηρίαση βάσει συστοιχίας), από τον προσωρινό πίνακα ως φθίνουσες τιμές oddPosition - 1 έως 0.

Όλα τα στοιχεία από το ήμισυ του προσωρινού πίνακα θα αποθηκευτούν στη μονή θέση του αρχικού πίνακα. Παρομοίως, θα αποθηκεύσουμε τις υπόλοιπες τιμές του δεύτερου μισού του προσωρινού πίνακα θα αποθηκευτούν σε ομοιόμορφη θέση του αρχικού πίνακα, με αυτόν τον τρόπο, μπορούμε να αναδιατάξουμε τον πίνακα έτσι ώστε τα στοιχεία σε ακόμη και μεγαλύτερες θέσεις και τα στοιχεία σε περίεργο Οι θέσεις στα περίεργα στοιχεία θα είναι μικρότερες από όλα τα στοιχεία πριν από αυτήν αντίστοιχα.

Αναδιάταξη της σειράς έτσι ώστε arr [i]> = arr [j] if i is even and arr [i] <= arr [j] if i is odd and 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 log n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n)  όπου «Ν»  είναι ο αριθμός των στοιχείων στον πίνακα.