Ερωτήματα για μετρήσεις στοιχείων πίνακα με τιμές σε δεδομένο εύρος


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Coursera DE Shaw Google PayU Snapdeal Times Internet Yahoo
Παράταξη bits Πρόβλημα ερωτήματος

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

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

Παράδειγμα

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

εξήγηση

Επειδή υπάρχουν 4 στοιχεία σε έναν πίνακα, δηλαδή 2, 4, 6 και 8 που βρίσκονται μεταξύ των 2 και 8, συνολικά.

Ερωτήματα για μετρήσεις στοιχείων πίνακα με τιμές σε δεδομένο εύρος

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

εξήγηση

Επειδή υπάρχουν 3 στοιχεία σε έναν πίνακα, που είναι 6, 8 και 10, που βρίσκεται μεταξύ των 5 και 10.

Αλγόριθμος

  1. Είδος ο πίνακας.
  2. Μάθετε το μεγαλύτερο ευρετήριο του πίνακα του στοιχείου y χρησιμοποιώντας δυαδική αναζήτηση, επιστρέψτε το μεγαλύτερο ευρετήριο.
  3. Μάθετε το μικρότερο ευρετήριο της συστοιχίας του στοιχείου x χρησιμοποιώντας δυαδική αναζήτηση, επιστρέψτε το μικρότερο ευρετήριο.
  4. Επιστρέψτε τη διαφορά μεταξύ του μεγαλύτερου δείκτη και του μικρότερου δείκτη και συν 1.

εξήγηση

Έχουμε δώσει έναν ακέραιο πίνακα και δύο αριθμούς x και y. Ζητήσαμε να μάθουμε τους συνολικούς αριθμούς που υπάρχουν σε έναν δεδομένο πίνακα που βρίσκεται μεταξύ των δεδομένων x και y. Βασικά, πρέπει να βρούμε το πλήθος των αριθμών μεγαλύτερο από το "x". Και ο αριθμός των αριθμών μικρότερος από το "y". Θα ταξινομήσουμε τον πίνακα. Ο λόγος πίσω από αυτό είναι ότι θα χρησιμοποιήσουμε μια μέθοδο δυαδικής αναζήτησης. Αυτό τροποποιείται επίσης.

Λάβετε το ευρετήριο του αριθμού y στον πίνακα χρησιμοποιώντας δυαδική αναζήτηση. Στη δυαδική αναζήτηση, προσπαθούμε να βρούμε το ευρετήριο στο οποίο υπάρχει το y. Συνεχίζουμε το βρόχο έως ότου η τιμή του χαμηλού είναι μικρότερη ή ίση με την τιμή του υψηλού. Συνήθως χαμηλός είναι ο 0ος δείκτης και υψηλός είναι ο τελευταίος δείκτης του πίνακα επειδή κάνουμε δυαδική αναζήτηση στους δείκτες του πίνακα. Η χρήση δυαδικής αναζήτησης μας επιτρέπει να απαντάμε σε ερωτήματα για μετρήσεις στοιχείων πίνακα με τιμές σε δεδομένο εύρος σε λογαριθμική χρονική πολυπλοκότητα για κάθε ερώτημα.

Θα λάβουμε τη μέση της χαμηλής και υψηλής τιμής και θα ελέγξουμε εάν το στοιχείο που υπάρχει στον πίνακα [mid] είναι μεγαλύτερο από ίσο με το x. Εάν αυτό ισχύει, ενημερώστε την τιμή του υψηλού έως τα μέσα του 1. Διαφορετικά ενημερώστε την τιμή του χαμηλού έως του μέσου +1. Το ίδιο πρέπει να εφαρμοστεί με το στοιχείο y. Αλλά σε αυτήν την περίπτωση, θα βρούμε τον μεγαλύτερο δείκτη και αντί να ελέγξουμε τον πίνακα [mid] είναι μεγαλύτερος από ίσος με y. Στη συνέχεια, συνεχίστε να ελέγχετε εάν ο πίνακας [mid] είναι μικρότερος από ίσος με y και ενημερώστε την τιμή χαμηλού έως μέσου + 1 και τιμής υψηλού έως μέσου 1.

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

Κώδικας

Κωδικός C ++ για να βρείτε τον αριθμό των στοιχείων του πίνακα σε ένα συγκεκριμένο εύρος

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}
4
3

Πρόγραμμα Java για να βρείτε τον αριθμό των στοιχείων του πίνακα σε ένα συγκεκριμένο εύρος

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

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}
4
3

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

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

Ο χρόνος για την εκτέλεση κάθε ερωτήματος θα είναι O (ημερολόγιο n) και για την ταξινόμηση του πίνακα μια φορά θα είναι O (n log n).

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Ο χώρος που εξετάσαμε είναι λόγω του χώρου που λαμβάνεται κατά την ταξινόμηση του πίνακα. Ο χώρος που απαιτείται για την αποθήκευση της εισόδου δεν εξετάζεται στο πρόβλημα "Ερωτήματα για μετρήσεις στοιχείων πίνακα με τιμές σε δεδομένο εύρος".