Μέγιστη απόσταση σε συστοιχία


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Google μαντείο
Παράταξη Χασίσι

Το πρόβλημα "Μέγιστη απόσταση σε συστοιχία" δηλώνει ότι σας δίνεται «Ν» όχι. των συστοιχιών και όλες οι συστοιχίες δίνονται σε αύξουσα σειρά. Ο στόχος σας είναι να βρείτε τη μέγιστη διαφορά / απόλυτη διαφορά δύο αριθμών σε ένα παράταξη και μπορούμε να ορίσουμε τη μέγιστη απόσταση μεταξύ δύο αριθμών ως abs | αβ |. Μπορείτε να επιλέξετε δύο αριθμούς για να σχηματίσετε διαφορετικούς πίνακες και να βρείτε το abs | αβ | ως η μέγιστη διαφορά.

Παράδειγμα

[  [1,2,3],
[0,2,3],
[1,4,5] ]
5

εξήγηση

Επειδή ο αριθμός «0» στη δεύτερη συστοιχία και ο αριθμός «5» στην τρίτη συστοιχία δίνει τη μέγιστη απόλυτη διαφορά σε ολόκληρο τον πίνακα.

Αλγόριθμος

  1. Δηλώστε μια μεταβλητή έξοδο και ορίστε την σε 0.
  2. Ορίστε την ελάχιστη τιμή ως βαρύ[0] [0].
  3. Ορίστε την τιμή του μέγιστου του varray μήκος πρώτης σειράς δηλαδή, ανώτατο όριο= varray [0] [0th μήκος σειράς-1].
  4. Βρείτε τη μέγιστη τιμή της διαφοράς μεταξύ του πρώτου στοιχείου του πρώτου πίνακα και του τελευταίου στοιχείου του δεύτερου πίνακα και της διαφοράς μεταξύ του τελευταίου στοιχείου του πρώτου πίνακα και του πρώτου στοιχείου του δεύτερου πίνακα
  5. Έτσι, βρείτε τη μέγιστη τιμή μεταξύ της τιμής που παράγεται από την παραπάνω γραμμή και της εξόδου και αποθηκεύστε την στην έξοδο.
  6. Βρείτε τη μικρότερη τιμή μεταξύ varray [i] [0] ελάχιστο και ορίστε το στο ελάχιστο.
  7. Βρείτε τη μεγαλύτερη τιμή μεταξύ varray [i] [σειρά_μεγέθους-1] ανώτατο όριο και ορίστε το στο μέγιστο.
  8. Επαναλάβετε την παραπάνω διαδικασία μέχρι το τέλος του πίνακα.
  9. Επιστροφή εξόδου.

Μια εξήγηση για τη μέγιστη απόσταση στο Array

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

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

Ας πάρουμε λοιπόν ένα παράδειγμα και να το λύσουμε:

Είσοδος: arr [] [] = {{0,2,4}, {2,3}, {4,5,6}};

Έξοδος = 0, μέγιστο = 4, ελάχιστο = 0, i = 1

έξοδος = std :: max (έξοδος,

std :: max (abs (varray [i] [varray [i] .size () - 1] - ελάχιστο),

abs (μέγιστο-varray [i] [0])))

Η έξοδος αποθηκεύεται ως 3

το μέγιστο παραμένει όπως είναι 4, το ελάχιστο παραμένει όπως είναι 0, i = 2

έξοδος = std :: max (έξοδος,

std :: max (abs (varray [i] [varray [i] .size () - 1] - ελάχιστο),

abs (μέγιστο-varray [i] [0])))

τις διαφορές μεταξύ του τελευταίου και του πρώτου στοιχείου διαφορετικών συστοιχιών

0 και 6 και από τα οποία το 6 είναι η μέγιστη διαφορά, έτσι η έξοδος θα γίνει 6

Και επιστροφή 6.

Μέγιστη απόσταση σε συστοιχία

Πρόγραμμα C ++ για μέγιστη απόσταση στο Array

#include <iostream>
#include<vector>
#include<cstdlib>
using namespace std;
int getMaxDistance(vector<vector <int>> varray)
{
    int output=0;
    int minimum=varray[0][0];
    int maximum=varray[0][varray[0].size()-1];

    for(int i = 1 ; i < varray.size() ; i++ )
    {
        output=std::max(output, std::max( abs( varray[i][varray[i].size()-1] - minimum ), abs(maximum-varray[i][0]) ) );
        minimum=std::min( minimum, varray[i][0] );
        maximum=std::max( maximum, varray[i][varray[i].size()-1]);
    }
    return output;

}
int main()
{
    vector<vector<int>> vec= {{0,2,4},{2,3,4},{4,5,6}};
    cout<<"Maximum distance is:"<<getMaxDistance(vec);
    return 0;
}
Maximum distance is: 6

Πρόγραμμα Java για μέγιστη απόσταση στο Array

import java.util.*;
import java.io.*;

class maximumDistance
{
    public static int getMaxDistance(int array[][])
    {
        int output=0;
        int minimum=array[0][0];
        int maximum=array[0][array[0].length-1];

        for(int i = 1 ; i < array.length ; i++ )
        {
            output=Math.max(output, Math.max(Math.abs( array[i][array[i].length-1] - minimum ), Math.abs(maximum-array[i][0]) ) );
            minimum=Math.min( minimum, array[i][0] );
            maximum=Math.max( maximum, array[i][array[i].length-1]);
        }
        return output;

    }
    public static void main(String args[])
    {
        int arr[][]= {{0,2,4},{2,3},{4,5,6}};
        System.out.println("Maximum distance is:"+(getMaxDistance(arr)));
    }
}
Maximum distance is: 6

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

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

O (n) όπου n είναι ο αριθμός των στοιχείων στον πίνακα. Επειδή διασχίζαμε απλώς τις σειρές του πίνακα 2D ή του πίνακα. Αλλά δεν περάσαμε ποτέ τις στήλες του πίνακα δεδομένων εισαγωγής.

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

Ο (1) καθώς χρησιμοποιήσαμε έναν σταθερό χώρο. Εφόσον έχουμε χρησιμοποιήσει μόνο σταθερό αριθμό μεταβλητών. Η προσέγγιση έχει συνεχή πολυπλοκότητα χώρου.

αναφορές