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


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Capgemini Πεζοπορώ MAQ o9 λύσεις TCS
Παράταξη Ταξινόμηση

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

Παράδειγμα

 εισόδου:

arr[]={2,4,-10,13,-7,-60,52,8,-19 }

Παραγωγή:

-10 -7 -60 -19 4 2 52 8 13

Επεξήγηση: Δεδομένου ότι όλοι οι αριθμοί μετατοπίζονται προς τα αριστερά και όλοι οι θετικοί αριθμοί μετατοπίζονται προς τα δεξιά.

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

Αλγόριθμος

  1. Ορίστε το j στο 0.
  2. Διασχίζοντας τον πίνακα από 0 σε n (αποκλειστικά, όπου το n είναι το μήκος του πίνακα).
    1. Ελέγξτε εάν οποιοδήποτε στοιχείο ενός πίνακα είναι μικρότερο από το 0,
      1. Ελέγξτε αν δεν πρέπει να είναι ίσο με j,
        1. Ανταλλάξτε τις τιμές των ευρετηρίων arr [i] και arr [j] και αυξήστε την τιμή του j.
  3. Εκτυπώστε τον πίνακα.

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

Μας δίνεται ένας πίνακας ακέραιου και ο πίνακας περιέχει τα θετικά και αρνητικά στοιχεία. Ζητήσαμε να μετατοπίσουμε όλα τα αρνητικά στοιχεία προς τα αριστερά και τους θετικούς αριθμούς προς τα δεξιά. Γι 'αυτό, πρόκειται ανταλλαγής όλους τους αριθμούς, που είναι θετικά και αρνητικά στοιχεία. Διασχίστε τον πίνακα πρώτα και, στη συνέχεια, ελέγξτε για τους αρνητικούς αριθμούς, εάν ο αριθμός είναι αρνητικός, τότε μόνο θα πάμε για ανταλλαγή των τιμών.

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

Έχουμε ελέγξει αυτήν την κατάσταση ότι το arr [i] είναι μικρότερο από 0, επειδή τακτοποιούμε μόνο τους αρνητικούς αριθμούς, όλοι οι αρνητικοί αριθμοί μετά την ανταλλαγή θα τακτοποιηθούν στα αριστερά του πίνακα και όλοι οι άλλοι θετικοί αριθμοί θα τακτοποιηθούν αυτόματα προς τα δεξιά του πίνακα. Μετά από όλα τα ανταλλακτικά που έχουμε κάνει, πρέπει απλώς να εκτυπώσουμε τον πίνακα στον οποίο εκτελέστηκαν οι πράξεις ανταλλαγής.

Εκτέλεση

Πρόγραμμα C ++ για Μετακίνηση όλων των αρνητικών αριθμών στην αρχή και θετικό στο τέλος

#include<iostream>

using namespace std;

void shiftIntegers(int arr[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            if (i != j)
                swap(arr[i], arr[j]);
            j++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shiftIntegers(arr, n);

    return 0;
}
-10 -7 -60 -19 4 2 52 8 13

Πρόγραμμα Java για μετακίνηση όλων των αρνητικών αριθμών στην αρχή και θετικό στο τέλος

class rearrangeNegativePositive
{
    public static void shiftIntegers(int arr[], int n)
    {
        int j = 0, temp;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (i != j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                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 args[])
    {
        int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
        int n = arr.length;

        shiftIntegers(arr, n);
        printArray(arr, n);
    }
}
-10 -7 -60 -19 4 2 52 8 13

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

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

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

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

Ο (1) καθώς δεν απαιτείται επιπλέον χώρος.

Συμπέρασμα

Πρόκειται για ένα πρόγραμμα που μετακινεί όλους τους αρνητικούς αριθμούς στην αρχή και το θετικό στο τέλος με σταθερό επιπλέον χώρο σε Java και C ++.

Αναφορά