Special Array With X Elements Greater Than or Equal X Leetcode Solution


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

Στο πρόβλημα, «Special Array With X Elements Greater Than or Equal X», μας δίνεται ένα παράταξη μη αρνητικών ακέραιων αριθμών. Πρέπει να βρούμε έναν ακέραιο X έτσι ώστε να υπάρχουν ακριβώς στοιχεία X μεγαλύτερα από ή ίσα με αυτόν στον πίνακα. Εάν δεν υπάρχει πιθανό X που να πληροί αυτήν την προϋπόθεση, πρέπει να πραγματοποιήσουμε έξοδο -1.

Παράδειγμα

1 2 3 4
-1
1 3 4 5
3

Προσέγγιση (Brute Force)

Είναι βέβαιο ότι εάν υπάρχει μια λύση X, τότε Το X θα είναι πάντα μοναδικό.

Απόδειξη:

Σκεφτείτε ότι υπάρχουν δύο λύσεις X και Y έτσι ώστε X! = Y. Ας υποθέσουμε ότι X <Y. Τώρα, ο αριθμός των στοιχείων μεγαλύτερων από ή ίσων με το X πρέπει να είναι X, καθώς το θεωρούμε ως λύση. Όμως, δεδομένου ότι το Y> X, υπάρχουν στοιχεία Υ μεγαλύτερα από ή ίσα με το Χ έτσι ώστε X! = Y. Ως εκ τούτου, η παραδοχή μας ότι το Χ είναι λύση είναι λάθος, εκτός αν τα Χ και Υ είναι ίσα.

Έτσι, υπάρχει πάντα μια μοναδική λύση, εάν υπάρχει λύση. Τώρα, μπορεί επίσης να συναχθεί το συμπέρασμα ότι εάν το X είναι μια λύση, τότε ο αριθμός των στοιχείων μεγαλύτερος από / ίσος με αυτό = X, που θα πρέπει να είναι μικρότερος από N, όπου N = μέγεθος του πίνακα (ως ο μέγιστος δυνατός αριθμός στοιχείων = Ν).

Έτσι, εάν υπάρχει μια λύση X, τότε πρέπει να βρίσκεται στην περιοχή [1, N].

Μπορούμε να ελέγξουμε για κάθε ακέραιο αριθμό στην περιοχή [1, N] εάν ο αριθμός των στοιχείων στη συστοιχία που είναι μεγαλύτερος ή ίσος με οποιονδήποτε ακέραιο στην περιοχή είναι ίσος με τον ίδιο τον ακέραιο. Για παράδειγμα, σκεφτείτε το Array = {1, 3, 4, 5}. Τώρα, τα 1 και 2 έχουν 4 και 3 στοιχεία μεγαλύτερα ή ίσα με αυτά στον πίνακα αντίστοιχα. Αριθμός στοιχείων μεγαλύτερος από / ίσος με 3 = 3. Άρα, το 3 είναι η μόνη λύση. Δεδομένου ότι διασχίζουμε ολόκληρο το δέντρο για να βρούμε τον αριθμό των στοιχείων μεγαλύτερο από κάθε ακέραιο στην περιοχή: [1, N], αυτή η προσέγγιση είναι αργή.

Αλγόριθμος

  1. Εκτελέστε έναν βρόχο από i = 1 έως i = N για να ελέγξετε τη λύση:
    • Μετρήστε τον αριθμό των στοιχείων μεγαλύτερο ή ίσο με "iστον πίνακα
      • Εάν ο αριθμός είναι ίσος με 'i", επιστροφή i
  2. απόδοση -1;

Εφαρμογή ειδικής σειράς με στοιχεία X μεγαλύτερη ή ίση με X Leetcode Solution

Πρόγραμμα C ++

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

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Πρόγραμμα Java

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

Ανάλυση πολυπλοκότητας του Special Array με X Elements Greater Than or Equal X Leetcode Solution

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

O (N * N), N = Μέγεθος του πίνακα. Στη χειρότερη περίπτωση, όταν το X = N είναι η λύση, κάνουμε συγκρίσεις O (N * N).

Διαστημικότητα

Ο (1). Χρησιμοποιείται μόνο σταθερός χώρος μνήμης.

Προσέγγιση (Βέλτιστη)

Μπορούμε να αποθηκεύσουμε τον αριθμό των εμφανίσεων όλων των στοιχείων σε έναν πίνακα, χρησιμοποιώντας έναν πίνακα. Σημειώστε ότι για οποιοδήποτε στοιχείο με τιμή μεγαλύτερη από N, μπορούμε να το μετρήσουμε ως εμφάνιση στοιχείου με τιμή N, επειδή η μέγιστη τιμή της λύσης μπορεί να είναι Ν.

Τώρα, η συχνότητα στοιχείων μεγαλύτερη ή ίση με X = συχνότητα X + συχνότητα όλων των στοιχείων μεγαλύτερη από X. Για να το βρούμε αυτό για κάθε στοιχείο στην περιοχή [1, N], πρέπει να έχουμε έναν πίνακα συχνοτήτων επιθήματος .

Έτσι, για κάθε ακέραιο αριθμό στον πίνακα, πρέπει να ορίσουμε συχνότητα [i] = συχνότητα [i] + συχνότητα [i + 1], για κάθε 'i«στην περιοχή [N - 1, 1], η οποία θα δημιουργήσει μια συστοιχία συχνοτήτων επιθήματος, αποθηκεύοντας αριθμό στοιχείων μεγαλύτερο ή ίσο με »i»  as συχνότητα [i].

Τώρα, λόγω του πίνακα αναζήτησης, μπορούμε να ελέγξουμε μια λύση για οποιοδήποτε ακέραιο στην περιοχή [1, N] in Ο (1) χρόνος. Αυτή είναι μια περίπτωση όπου εμείς ανταλλαγή μνήμη για να βελτιωθεί εγκαίρως. Δεδομένου ότι ο πίνακας έχει μέγεθος Ν, δεν ανησυχούμε επίσης για τα όρια μνήμης.

 

Special Array With X Elements Greater Than or Equal X Leetcode Solution

Αλγόριθμος

  1. Αρχικοποίηση a συχνότητα πίνακας μεγέθους N, με κάθε τιμή ως μηδέν
  2. Για κάθε στοιχείο i  στον πίνακα:
    1. If i > N, συχνότητα αύξησης [N]
    2. Συχνότητα αύξησης [i]
  3. Δημιουργήστε έναν πίνακα αθροίσματος επιθήματος από συχνότητα όπως και:
    1. Για κάθε στοιχείο που κυμαίνεται από i = Ν - 1 προς την i = 0
      1. σειρά συχνότητα[i] = συχνότητα [i] + συχνότητα [i + 1]
  4. Εκτελέστε ένα βρόχο από i = 1 έως i = Ν
    1. If i == συχνότητα [i], ΕΠΙΣΤΡΟΦΗ i
  5. επιστροφή -1

Εφαρμογή ειδικής σειράς με στοιχεία X μεγαλύτερη ή ίση με X Leetcode Solution

Πρόγραμμα C ++

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

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

Πρόγραμμα Java

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

Ανάλυση πολυπλοκότητας του Special Array με X Elements Greater Than or Equal X Leetcode Solution

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

ΕΠΙ), N = Μέγεθος του πίνακα. Μπορούμε να ελέγξουμε για οποιοδήποτε ακέραιο χρόνο O (1), οπότε στη χειρότερη περίπτωση χρησιμοποιούμε O (N) ώρα.

Διαστημικότητα

ΕΠΙ). Ο γραμμικός χώρος μνήμης χρησιμοποιείται για την αποθήκευση συχνοτήτων.