Μετατροπή πίνακα σε μειωμένη μορφή


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις LinkedIn Snapchat Xome Yahoo
Παράταξη Χασίσι Ταξινόμηση

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

Το πρόβλημα «Μετατροπή πίνακα σε μειωμένη μορφή» δηλώνει ότι σας δίνεται μια σειρά από ακέραιους αριθμούς και διακριτά στοιχεία. Η δήλωση προβλήματος ζήτησε να μειωθεί ο πίνακας με τέτοιο τρόπο ώστε οι νέοι αριθμοί να τοποθετηθούν στον πίνακα εντός του εύρους 0 έως n-1. Ο μικρότερος αριθμός του πίνακα πρέπει να θεωρείται 0, μεγαλύτερος από αυτόν του 1. Και συνεχώς ο αριθμός n-1 είναι το μεγαλύτερο στοιχείο του πίνακα.

Παράδειγμα

arr[]={20,10,35,42,8}
2 1 3 4 0

Επεξήγηση: Πρέπει να τοποθετήσουμε τον αριθμό πίνακα στη μειωμένη φόρμα εντός 0 έως το εύρος n-1. Μπορούμε να δούμε ότι το 8 είναι το μικρότερο, οπότε είναι 0. 10 είναι το επόμενο, έτσι είναι 1, 20 είναι 2 και ούτω καθεξής.

 

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

1. Declare a temporary array of size the same as the original array.
2. Copy all the values of the given array into the declared array.
3. Sort that array in which we have copied the value of the original array.
4. Declare a map and set an integer variable ‘val’ to 0.
5. Traverse the array and store the value of the temp array’ element as a key into the map and a val value and increasing the count of ‘val’ by 1 every time.
6. Traverse the original array from 0 to n-1.
  1. Place the value of the map’s key into the array.
7. Print the original array in which we replace the value of the map.

εξήγηση

Έχουμε δώσει μια σειρά από ακέραιους αριθμούς, πρέπει να μειώσουμε τον πίνακα με τέτοιο τρόπο ώστε κάθε αριθμός στον αρχικό πίνακα να παίρνει μια τιμή από εύρος 0 έως n-1 χωρίς να λείπει καμία τιμή από το εύρος. Αυτό σημαίνει ότι εάν έχουμε δώσει 5 αριθμούς στον πίνακα τότε θα τοποθετήσουμε τον αριθμό από 0 έως 4 συνολικά σε κάθε θέση ενός στοιχείου του αρχικού πίνακα.

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

Ο χάρτης θα αποθηκεύσει τις τιμές του προσωρινού πίνακα που δημιουργήσαμε ως κλειδί και τώρα ο προσωρινός πίνακας ταξινομείται έτσι ώστε να μπορούμε να τοποθετήσουμε τον αριθμό από το o στο n-1. Θα διασχίσουμε τον πίνακα και θα τοποθετήσουμε τα στοιχεία ως κλειδί και val στην τιμή του κλειδιού. Η αξία του val θα αυξάνεται κατά 1 κάθε φορά που διασχίζουμε με μια νέα τιμή, οπότε κυμαίνεται αυτόματα από 0 έως n-1.

Διασχίστε τον αρχικό πίνακα και εισαγάγετε όλες τις τιμές του χάρτη στον αρχικό πίνακα ή μπορούμε να πούμε ότι θα αντικαταστήσουμε τον αρχικό πίνακα με αυτές τις νέες τιμές. Εκτυπώστε αυτά τα στοιχεία του αρχικού πίνακα καθώς το έχουμε ήδη μειώσει με τη μορφή εύρους 0 έως n-1.

Μετατροπή πίνακα σε μειωμένη μορφή

Κώδικας

Κωδικός C ++ για μετατροπή ενός πίνακα σε μειωμένη μορφή

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void convert(int arr[], int n)
{
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));

    sort(temp, temp + n);

    unordered_map<int, int> umap;

    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;

    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {20,10,35,42,8};
    int n = sizeof(arr)/sizeof(arr[0]);

    convert(arr, n);
    cout << "Converted Array is : \n";
    printArr(arr, n);
    return 0;
}
Converted Array is :
2 1 3 4 0

 

Κωδικός Java για τη μετατροπή ενός πίνακα σε μειωμένη μορφή

import java.util.HashMap;
import java.util.Arrays;

class ReducedArray
{
    public static void convert(int arr[], int n)
    {
        int temp[] = arr.clone();

        Arrays.sort(temp);

        HashMap<Integer, Integer> umap = new HashMap<>();

        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);


        System.out.println("Converted Array is : ");
        for (int i = 0; i < n; i++)
        {
            arr[i] = umap.get(arr[i]);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args)
    {

        int arr[] = {20,10,35,42,8};
        int n = arr.length;
        convert(arr, n);

    }
}
Converted Array is :
2 1 3 4 0

 

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

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

We ταξινομημένο τον πίνακα εισαγωγής μας. Να γιατί O (n Log n) όπου «Ν» είναι το μέγεθος του πίνακα.

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

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