Subarrays με διαφορετικά στοιχεία


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Cisco Χωρίς χρέωση Times Internet Zoho
Παράταξη Χασίσι Hashing

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

Το "Subarrays με διαφορετικά στοιχεία" δηλώνει ότι σας δίνεται μια σειρά από ακέραια στοιχεία. Η δήλωση προβλήματος ζητά να βρει το άθροισμα των μήκους των συνεχόμενων υπο-συστοιχιών που έχουν όλα τα στοιχεία διαφορετικά μεταξύ τους.

Παράδειγμα

arr[] = {3, 1, 2, 1}
4

Επεξήγηση: Οι υπο-συστοιχίες είναι ⇒ (3, 1, 2), (3, 1), (1, 2), (2,1), (3), (1), (2), (1)

Το συνολικό μήκος όλων των στοιχείων είναι (3 + 2 + 2 + 2 + 1 + 1 + 1 + 1) = 10.

Subarrays με διαφορετικά στοιχεία

arr[] = {3, 5, 8, 9}
20

Επεξήγηση: Οι υπο-συστοιχίες είναι ⇒ (3), (5), (8), (9), (3, 5), (5, 8), (8, 9), (3, 5, 8), (5, 8, 9), (3, 5, 8, 9)

Το συνολικό μήκος όλων των στοιχείων είναι (1 + 1 + 1 + 1 + 2 + 2 + 2 +3 +3 +4) = 10.

Αλγόριθμος για εύρεση Subarrays με διαφορετικά στοιχεία

1. Declare a map.
2. Set output and j to 0.
3. Traverse the array from i=0 to i<n(length of an array).
  1. While j is less than n and if a set doesn’t contain the value of arr[j].
    1. Insert all the values of arr [j].
  2. Update the output to output +=((j - i) * (j - i + 1))/2.
  3. Remove the arr[i] from Set.
4. Return output.

εξήγηση

Έχουμε δώσει ένα ακέραιος αριθμός παράταξη. Ο στόχος μας είναι να ανακαλύψουμε το άθροισμα του μήκους όλων των υπο-πίνακες που είναι γειτονικά και έχουν μόνο ξεχωριστά στοιχεία. Θα χρησιμοποιήσουμε ένα σετ. Το σετ παρέχει μια δυνατότητα αφαίρεσης αντιγραμμένων ή κοινών στοιχείων από ένα σύνολο. Ορίστε j σε 0 και έξοδο σε 0.

Ξεκινήστε διασχίζοντας τον πίνακα και χρησιμοποιήστε ένα ενώ βρόχος. Ορίστε την τιμή του j στο 0 και στο εσωτερικό ενώ βρόχος θα διασχίσουμε τον βρόχο ενώ αυξάνουμε το j. Ορίστε ορισμένες συνθήκες σε αυτό, ενώ το j είναι μικρότερο από n, δηλαδή, το μήκος του πίνακα και επίσης αν βρεθεί ότι το Set περιέχει την τιμή του arr [j]. Ας εξετάσουμε ένα παράδειγμα:

Arr [] = {3, 1, 2, 1}

Θα διασχίζουμε τον πίνακα επιλέγοντας κάθε στοιχείο ταυτόχρονα, ας υποθέσουμε ότι θα επιλέξουμε 3 την πρώτη φορά, στο arr [j], η ιδέα είναι να διατηρήσουμε τον εξωτερικό βρόχο σταθερό για λίγο καιρό αυτό το 3 θα ξεκινήσει ενώ βρόχος, καθώς το j αρχικοποιείται ως 0 και το σετ δεν περιέχει 3 για πρώτη φορά, οπότε θα εισέλθει στο a ενώ βρόχος και εισάγετε το arr [j] σημαίνει 3 και αυξήστε το j ++, θα επιλέξει το επόμενο στοιχείο ως 1, σετ δεν το περιέχει έτσι θα εισαχθεί σε ένα σετ, έπειτα έρχεται 2 και έπειτα έρχεται 1, αλλά αυτή τη φορά, το 1 είναι ήδη στο βρόχο, οπότε θα βγει από το ενώ βρόχος.

Τώρα, όταν βγαίνουμε από το βρόχο, έχουμε αυξήσει την τιμή του j, οπότε θα ενημερώσουμε την έξοδο σύμφωνα με αυτό. Και για περαιτέρω διασταύρωση, πρέπει να αφαιρέσουμε το στοιχείο του πίνακα, έτσι ώστε να μπορέσουμε να μάθουμε το πιθανό μήκος του αθροίσματος των διακριτών στοιχείων στον υπο-πίνακα. Και τέλος, θα επιστρέψουμε αυτήν την έξοδο.

Κώδικας

C ++ για να βρείτε subarrays με διαφορετικά στοιχεία

#include<iostream>
#include<unordered_set>

using namespace std;

int getLength(int arr[], int n)
{
    unordered_set<int> SET;

    int j = 0, output = 0;
    for (int i=0; i<n; i++)
    {
        while (j < n && SET.find(arr[j]) == SET.end())
        {
            SET.insert(arr[j]);
            j++;
        }
        output += ((j - i) * (j - i + 1))/2;
        SET.erase(arr[i]);
    }
    return output;
}
int main()
{
    int arr[] = {3, 1, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getLength(arr, n);
    return 0;
}
13

Κωδικός Java για να βρείτε subarrays με διαφορετικά στοιχεία

import java.util.Set;
import java.util.HashSet;

class LengthOfDistinctElements
{
    public static int getLength(int[] arr, int n)
    {
        Set<Integer> SET = new HashSet<>();
        int j = 0, output = 0;
        for (int i = 0; i < n; i++)
        {
            while (j < n && !SET.contains(arr[j]))
            {
                SET.add(arr[j]);
                j++;
            }
            output += ((j - i) * (j - i + 1)) / 2;
            SET.remove(arr[i]);
        }
        return output;
    }
    public static void main(String[] args)
    {
        int[] arr = { 3, 1, 2,1  };
        int n = arr.length;
        System.out.println(getLength(arr, n));
    }
}
13

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

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

Έχουμε διασχίσει τον πίνακα και η χρήση του HashSet επιτρέπει την εκτέλεση εισαγωγής και άλλες τέτοιες λειτουργίες στο O (1). Έτσι επιτυγχάνουμε ΕΠΙ) χρονική πολυπλοκότητα όπου "N" είναι ο αριθμός των στοιχείων στον πίνακα.

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

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