Τριμερής κατάτμηση ενός πίνακα γύρω από ένα δεδομένο εύρος


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις BankBazaar BlackRock Capital One Ακρόπολη Fab Εργαστήρια Moonfrog Synopsys Twilio Yahoo
Παράταξη

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

Σας δίνεται ένα παράταξη of ακέραιους αριθμούς και μια σειρά χαμηλής και υψηλής αξίας. Το πρόβλημα "Τρισδιάστατη κατάτμηση ενός πίνακα γύρω από ένα συγκεκριμένο εύρος" ζητά να χωριστεί ο πίνακας έτσι ώστε ο πίνακας να χωριστεί σε τρία μέρη. Τα διαμερίσματα των συστοιχιών θα είναι:

  1. Τα στοιχεία του πρώτου διαμερίσματος θα είναι μικρότερα από τη χαμηλή τιμή,
  2. Το επόμενο διαμέρισμα έτσι ώστε τα στοιχεία να βρίσκονται εντός του δεδομένου εύρους θα είναι σε αυτό το διαμέρισμα και το
  3. Αριθμοί μεγαλύτεροι από το highValue θα είναι το τρίτο διαμέρισμα του πίνακα.

Παράδειγμα

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30
2 5 1 12 4 9 23 76 56 45 87

εξήγηση

Το lowValue είναι 15, έτσι ώστε οι αριθμοί στην αριστερή πλευρά να είναι μικρότεροι από το lowValue.

Το εύρος είναι μεταξύ 15 και 30, το 23 είναι ο αριθμός που βρίσκεται μεταξύ αυτού του εύρους

Το highValue είναι 30, όλοι οι αριθμοί μεγαλύτεροι από το highValue θα βρίσκονται στη δεξιά πλευρά.

Τριμερής κατάτμηση ενός πίνακα γύρω από ένα δεδομένο εύρος

Αλγόριθμος

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

εξήγηση

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

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

Κώδικας

Κωδικός C ++ για επίλυση Τριμερής κατάτμηση ενός πίνακα γύρω από ένα δεδομένο εύρος

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
2 5 1 12 4 9 23 76 56 45 87

Κωδικός Java για επίλυση Τριμερής κατάτμηση ενός πίνακα γύρω από ένα δεδομένο εύρος

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

        for (int i=0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");

        }
    }
}
2 5 1 12 4 9 23 76 56 45 87

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

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Δεδομένου ότι έχουμε διασχίσει τα στοιχεία του πίνακα, η πολυπλοκότητα του χρόνου είναι γραμμική.

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

Ο (1) καθώς δεν απαιτείται επιπλέον χώρος. Ο ίδιος ο αλγόριθμος είναι επί τόπου αλγόριθμος και ενημερώνει τον αρχικό δεδομένο πίνακα. Έτσι η διαστημική πολυπλοκότητα του αλγορίθμου είναι σταθερή ενώ το πρόγραμμα είναι γραμμικό.