Περίληψη Λύση Leetcode Ranges


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Facebook Yandex
Παράταξη

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

Συνοπτικά προβλήματα Ranges a ταξινομημένο μοναδικό Δίδεται ακέραιος πίνακας. Πρέπει να κάνουμε μικρότερο ταξινομημένο λίστα εύρους που καλύπτει όλους τους αριθμούς σε παράταξη ακριβώς μια φορά δηλαδή κάθε στοιχείο του πίνακα καλύπτεται από ακριβώς ένα από τα εύρη.

Κάθε εύρος [a, b] στη λίστα πρέπει να εξάγεται ως:

"A-> b" εάν a! = B
"A" αν a == β

Παράδειγμα

nums = [0,1,2,4,5,7]
["0->2","4->5","7"]

Επεξήγηση:

Τα εύρη είναι:
Το "0-> 2" καλύπτει τους αριθμούς {0, 1, 2}
Το "4-> 5" καλύπτει τους αριθμούς {4, 5}
Το "7" καλύπτει τους αριθμούς {7}

Ως εκ τούτου, καλύπτει όλους τους αριθμούς του πίνακα ακριβώς μία φορά.

nums = [0,2,3,4,6,8,9]
["0","2->4","6","8->9"]

Επεξήγηση:

Τα εύρη είναι:
[0,0] -> "0"
[2,4] -> "2-> 4"
[6,6] -> "6"
[8,9] -> "8-> 9"

Προσέγγιση

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

Περίληψη Λύση Leetcode Ranges

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

Αλγόριθμος

  1. Δημιουργήστε μια λίστα συμβολοσειρών για να αποθηκεύσετε το αποτέλεσμα.
  2. Ξεκινήστε να διασχίζετε τον πίνακα από I = 0 να i<N, (N είναι το μέγεθος του πίνακα) σε ένα βρόχο.
    • Σημειώστε τον αριθμό στο τρέχον ευρετήριο ως Εκκίνηση του εύρους.
    • Διασχίστε τον πίνακα ξεκινώντας από το τρέχον ευρετήριο και βρείτε το τελευταίο στοιχείο του οποίου η διαφορά από το προηγούμενο στοιχείο είναι ακριβώς 1, δηλαδή αριθμοί [i + 1] == αριθμοί [i] +1
    • Επισημάνετε αυτό το στοιχείο ως τέλος του εύρους.
    • Τώρα εισάγετε αυτό το σχηματισμένο εύρος στο αποτέλεσμα λίστα. Και επαναλάβετε για τα υπόλοιπα στοιχεία.
  3. Επέστρεψε το αποτέλεσμα λίστα.

Εκτέλεση

Πρόγραμμα C ++ για Περίληψη Λύση Leetcode Ranges

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

vector<string> summaryRanges(vector<int>& nums) 
{
    vector<string> res;
    int i=0,n=nums.size();
    while(i<n)
    {
        int start,end;

        start=nums[i];            
        while(i+1<n && nums[i+1]==nums[i]+1) i++;
        end=nums[i];

        if(start==end)
            res.push_back(to_string(start));
        else
            res.push_back(to_string(start) + "->" + to_string(end));

        i++;
    }

    return res;
}

int main() 
{   
    vector<int> nums={0,1,2,4,5,7};
    vector<string> res= summaryRanges(nums);
    
    for(auto str:res) cout<< str <<endl;
    
    return 0; 
}
0->2
4->5
7

Πρόγραμμα Java για Περίληψη Λύση Leetcode

import java.util.*;
class Rextester{
    
    public static List<String> summaryRanges(int[] nums) 
    {      
        List<String> res= new ArrayList<String>();
        
        int i=0,n=nums.length;
        while(i<n)
        {
            int start,end;
            
            start=nums[i];            
            while(i+1<n && nums[i+1]==nums[i]+1) i++;
            end=nums[i];
            
            if(start==end)
                res.add(start + "");
            else
                res.add( start + "->" + end );
            
            i++;          
        }
        
        return res;
    }
    
  public static void main(String args[])
    {
        int[] nums={0,1,2,4,5,7};
        List<String> res= summaryRanges(nums);
        
        for(String str:res)
            System.out.println(str);
    }
}
0->2
4->5
7

Ανάλυση πολυπλοκότητας για συνοπτική λύση Leetcode Solution

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

ΕΠΙ) : Όπου N είναι το μέγεθος της δεδομένης συστοιχίας. Αν και χρησιμοποιούμε δύο ένθετους βρόχους, αλλά κάθε στοιχείο επισκέπτεται μόνο μία φορά. Ως εκ τούτου, η πολυπλοκότητα του χρόνου είναι O (N).

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

O (1): Δεν χρησιμοποιούμε κανένα βοηθητικό χώρο εκτός από την επιστροφή της λίστας συμβολοσειρών.