Μετρήστε Subarrays με Ίδια Ζυγά και Μονά Στοιχεία


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Accenture Γεγονότα Φανατικοί
Παράταξη Χασίσι

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

Παράδειγμα

Εισαγωγή

arr [] = {2, 5, 1, 6};

Παραγωγή

3

εξήγηση

Καθώς υπάρχουν ⇒ {2, 5}, {1, 6}, {2, 5, 1, 6}

Εισαγωγή

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

Παραγωγή

7

Αλγόριθμος

  1. Δηλώστε δύο πίνακες, θετικό και αρνητικό Αριθμός μεγέθους n + 1.
  2. Ορίστε την καταμέτρηση και την έξοδο σε 0 και ορίστε το positiveNum [0] σε 1.
  3. Διασχίστε τον πίνακα από i = 0, έως i
    1. Ελέγξτε αν το bitwise και η λειτουργία arr [i] & 1 είναι ίση με 1,
      1. Εάν ισχύει, αυξήστε τον αριθμό κατά 1.
    2. Διαφορετικά, μειώστε τον αριθμό κατά 1.
    3. Εάν η μέτρηση είναι μικρότερη από 0, τότε προσθέστε την έξοδο στο negativeNum [-count] και αποθηκεύστε την στην έξοδο.
    4. Διαφορετικά, προσθέστε την έξοδο στο positiveNum [count] και αποθηκεύστε την στην έξοδο.
  4. Επιστροφή εξόδου.

εξήγηση

Θα φτιάξουμε τις δύο συστοιχίες κατακερματισμού, μία για την αποθήκευση της θετικής διαφοράς και μία για τις αρνητικές διαφορές. Με τις διαφορές, θέλουμε να πούμε, θα ανακαλύψουμε τις διαφορές μεταξύ των συχνοτήτων των μονών και ακόμη και των ακέραιων αριθμών. Ρυθμίζοντας την έξοδο σε 0, σε αυτό, θα ενημερώσουμε την απάντησή μας, θα μετρήσουμε σε 0, αυτό θα διατηρήσει τον αριθμό διαφοράς. Αφού δηλώσετε δύο συστοιχίες κατακερματισμού, ορίστε το θετικό σε 1, positiveNum [0] = 1.

Θα διασχίσουμε τον πίνακα και θα ελέγξουμε αν είναι μονή ή θετική, γι 'αυτό θα χρησιμοποιήσουμε τον τελεστή Bitwise AND, εάν χρησιμοποιήσουμε τον τελεστή AND μεταξύ 1 και οποιασδήποτε τιμής, θα λάβουμε τα δύο αποτελέσματα, είτε 1 είτε 0, εάν ο ο αριθμός είναι περίεργος θα δώσει 1 ως έξοδο, αν είναι ακόμη και τότε, δίνει 0 ως έξοδο. Εάν ο αριθμός βρεθεί ότι είναι 1, τότε θα αυξήσουμε τον αριθμό κατά 1, αλλιώς μπορεί να είναι μόνο 0, οπότε θα μειώσουμε την ίδια τιμή μέτρησης κατά 1.

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

Εκτέλεση

Πρόγραμμα C ++ για Count Subarrays με Ίδια Ζυγά και Μονά Στοιχεία

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

    for (int i = 0; i < n; i++)
    {
        if ((arr[i] & 1) == 1) count++;
        else count--;

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}
Even Odd Sub-Arrays are: 7

Πρόγραμμα Java για Count Subarrays με Ίδια Ζυγά και Μονά Στοιχεία

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) == 1) count++;
            else count--;

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}
Even Odd Sub-Arrays are: 7

Ανάλυση πολυπλοκότητας για Count Subarrays με Ίδια Ζυγά και Μονά Στοιχεία

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

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

O (2n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.