Μετακινήστε όλα τα αρνητικά στοιχεία στο τέλος με επιτρεπόμενο επιπλέον χώρο


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Capital One Citrix IBM SAP Labs Ταξί4Sure Twilio
Παράταξη

Δήλωση προβλήματος

"Μετακινήστε όλα τα αρνητικά στοιχεία στο τέλος με επιτρεπόμενο επιπλέον χώρο" δηλώνει ότι σας δίνεται ένας πίνακας που περιέχει θετικούς και αρνητικούς αριθμούς και τα δύο. Η δήλωση προβλήματος ζητά να μετακινήσετε όλα τα αρνητικά στοιχεία στο τελευταίο του πίνακα.

Παράδειγμα

arr[] = { 1,2,-3,-5,2,7,-9,-11 }
1, 2, 2, 7, -3, -5, -9, -11
Επεξήγηση: Όλες οι αρνητικές τιμές έχουν μετακινηθεί στο τελευταίο του πίνακα. Και είναι στην αρχική σειρά επίσης.

Αλγόριθμος για Μετακίνηση όλων των αρνητικών στοιχείων στο τέλος με επιτρεπόμενο επιπλέον χώρο

1. Declare an array same as the size of the original array.
2. Traverse the array and check if any number is greater than or equal to 0,
    1. If true then copy that number from the 0th position of the array we created.
3. Now traverse the array and check if any of the numbers is less than 0.
    1. If true, then copy that value to the array we created from the next position where the positive number ends.
4. Now copy that temporary array we created into the original array and print that array.

εξήγηση

Μας δίνεται ένα ακέραιος αριθμός πίνακας που περιέχει τόσο αρνητικούς όσο και θετικούς αριθμούς. Ζητήσαμε να αναδιατάξουμε τον πίνακα με τέτοιο τρόπο ώστε να πρέπει να μετακινήσουμε όλα τα αρνητικά στοιχεία στο τελευταίο / τέλος του πίνακα. Τότε θα διασχίζουμε τον πίνακα για θετικά και αρνητικά στοιχεία ξεχωριστά. Πρώτον, πρέπει να εκτελέσουμε πράξεις σε θετικά στοιχεία όπου πρέπει να τα τραβήξουμε προς τα αριστερά. Και μετά μετακινήστε όλα τα αρνητικά στοιχεία προς τα δεξιά.

Πρέπει να δημιουργήσουμε έναν επιπλέον πίνακα ίδιου μεγέθους με αυτόν του αρχικού πίνακα. Επειδή σε αυτό, θα αποθηκεύουμε την επιθυμητή διάταξη αριθμών. Παραλαβή ενός μεταβλητού δείκτη και αρχικοποίησή του ως 0. Αυτή η μεταβλητή θα μας βοηθήσει να διακρίνουμε μεταξύ των θετικών και αρνητικών στοιχείων. Τώρα δημιουργήσαμε έναν πίνακα. Θα βάλουμε τους θετικούς αριθμούς από τον αρχικό πίνακα στον προσωρινό πίνακα.

Θα ελέγξουμε ενώ διασχίζουμε εάν τα στοιχεία του πίνακα είναι μεγαλύτερα ή ίσα με 0, τότε θα αντιγράψουμε μόνο αυτό το στοιχείο στον προσωρινό πίνακα, από την αρχική θέση του προσωρινού πίνακα. Επίσης, αυξάνουμε ταυτόχρονα την τιμή του δείκτη, οπότε από την τελευταία φορά που αντιγράφουμε το θετικό στοιχείο έχουμε έναν δείκτη τιμής από το επόμενο στοιχείο όπου θα αποθηκευτεί, με τη βοήθεια αυτού θα πιέσουμε επιτέλους όλα τα αρνητικά στοιχεία.

Τώρα θα πάμε για να διασχίσουμε ξανά τον πίνακα και να ελέγξουμε εάν καθένα από τα στοιχεία είναι μικρότερο από το 0 εάν είναι μηδέν, τότε αρχίστε να πιέζετε αυτήν την τιμή στον προσωρινό πίνακα από την τιμή ευρετηρίου όπου σταματήσαμε. Επιτέλους, αντιγράψτε αυτόν τον πίνακα στον αρχικό πίνακα και μετά εκτυπώστε τον ή απλά εκτυπώστε τον προσωρινό πίνακα, και οι δύο είναι τα ίδια πράγματα. Και έχουμε την απαιτούμενη έξοδο.

Μετακινήστε όλα τα αρνητικά στοιχεία στο τέλος με επιτρεπόμενο επιπλέον χώρο

Κώδικας

Κωδικός C ++ για Μετακίνηση όλων των αρνητικών στοιχείων στο τέλος με επιτρεπόμενο επιπλέον χώρο

#include<bits/stdc++.h>
using namespace std;

void segregateElements(int arr[], int n)
{
    int temp[n];

    int j = 0;

    for (int i = 0; i < n ; i++)
        if (arr[i] >= 0 )
            temp[j++] = arr[i];

    if (j == n || j == 0)
        return;

    for (int i = 0 ; i < n ; i++)
        if (arr[i] < 0)
            temp[j++] = arr[i];

    memcpy(arr, temp, sizeof(temp));
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
    int n = sizeof(arr)/sizeof(arr[0]);

    segregateElements(arr, n);
    printArray(arr,n);

    return 0;
}
1 2 2 7 -3 -5 -9 -11

Κωδικός Java για Μετακίνηση όλων των αρνητικών στοιχείων στο τέλος με επιτρεπόμενο επιπλέον χώρο

import java.util.Arrays;

class moveNegativeElement
{
    public static void segregateElements(int arr[], int n)
    {
        int temp[] = new int[n];

        int j = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] >= 0)
                temp[j++] = arr[i];

        if (j == n || j == 0)
            return;

        for (int i = 0; i < n; i++)
            if (arr[i] < 0)
                temp[j++] = arr[i];

        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }
    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 arg[])
    {
        int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
        int n = arr.length;

        segregateElements(arr, n);
        printArray(arr,n);

    }
}
1 2 2 7 -3 -5 -9 -11

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ) όπου "N" είναι τα στοιχεία του πίνακα. Απλώς περάσαμε από τον πίνακα λόγω του οποίου έχουμε επιτύχει γραμμική πολυπλοκότητα χρόνου.

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

ΕΠΙ) όπου "N" είναι τα στοιχεία του πίνακα. Δημιουργήσαμε έναν επιπλέον πίνακα για προσωρινή χρήση όπου έχουμε αποθηκεύσει τα στοιχεία με τον επιθυμητό τρόπο.