Η μέγιστη διαφορά μεταξύ συχνότητας δύο στοιχείων έτσι ώστε το στοιχείο που έχει μεγαλύτερη συχνότητα είναι επίσης μεγαλύτερη


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Accenture Απολύτως αμαζόνα VMware
Παράταξη Χασίσι Ταξινόμηση

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

Παράδειγμα

εισόδου:

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

Παραγωγή:

2

Επεξήγηση:

Η συχνότητα 4 → 3

Η συχνότητα 2 → 2

και τη συχνότητα 3 → 1

4 (3) - 3 (1) = 2 (Οι ακέραιοι αριθμοί είναι επίσης μεγαλύτεροι και η μέγιστη συχνότητα).

Αλγόριθμος

  1. Δήλωση α χάρτη και ένας πίνακας λέει «απόσταση» μήκους n.
  2. Μετρήστε και αποθηκεύστε το συχνότητα στοιχείων στον χάρτη και ταυτόχρονα αποθηκεύστε τις τιμές του πίνακα σε έναν πίνακα απόστασης.
  3. Ταξινόμηση του πίνακα απόστασης.
  4. Ορίστε ελάχιστο σε n + 1 και έξοδο σε 0.
  5. Διασχίστε τον πίνακα, ενώ i
    1. Βρείτε το μέγιστο μεταξύ της εξόδου και της διαφοράς μεταξύ της τιμής της απόστασης [i] και της ελάχιστης και αποθηκεύστε την στην έξοδο.
    2. Βρείτε το ελάχιστο μεταξύ της ελάχιστης και της τιμής της απόστασης [i] και αποθηκεύστε το στο ελάχιστο.
  6. Επιστροφή εξόδου.

εξήγηση

Μας δίνεται ένας ακέραιος και πρέπει να ανακαλύψουμε τη μέγιστη διαφορά μεταξύ της συχνότητας δύο στοιχείων έτσι ώστε το στοιχείο που έχει μεγαλύτερη συχνότητα θα πρέπει επίσης να είναι μεγαλύτερο από έναν άλλο ακέραιο με τη χαμηλότερη συχνότητα και επίσης να είναι μικρότερο από έναν μεγαλύτερο ακέραιο. Θα χρησιμοποιήσουμε Hashing διαλογή που θα μας βοηθήσει να δημιουργήσουμε αποτελεσματικό κώδικα. Πρώτον, θα δηλώσουμε έναν χάρτη και έναν ακέραιο πίνακα που ονομάζεται απόσταση με το ίδιο μέγεθος με τον δεδομένο πίνακα.

Ενώ διασχίζουμε τον πίνακα για να αποθηκεύσουμε και να μετρήσουμε τη συχνότητα των στοιχείων πίνακα, πρέπει επίσης να αποθηκεύσουμε την τιμή του πίνακα [i] σύμφωνα με τον αλγόριθμό μας. Θα ορίσουμε την τιμή της εξόδου στο 0 και το ελάχιστο σε n + 1. Αυτή η ελάχιστη τιμή μας βοηθά να βρούμε το ελάχιστο μεταξύ όλων των συχνοτήτων και στη μεταβλητή εξόδου πρόκειται να αποθηκεύσουμε τη μέγιστη διαφορά μας. Τώρα, πρέπει να ταξινομήσουμε τον πίνακα στον οποίο αποθηκεύουμε τις τιμές (πίνακας απόστασης).

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

Εκτέλεση

Πρόγραμμα C ++ για Μέγιστη διαφορά μεταξύ συχνότητας δύο στοιχείων

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

Πρόγραμμα Java για μέγιστη διαφορά μεταξύ συχνότητας δύο στοιχείων

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

Ανάλυση πολυπλοκότητας για τη μέγιστη διαφορά μεταξύ της συχνότητας δύο στοιχείων

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

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

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

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