Διακριτά παρακείμενα στοιχεία σε έναν πίνακα


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Coursera DE Shaw Πεζοπορώ IBM Κουλίζα Ναγκάρο Opera Δωμάτια OYO Zoho
Παράταξη

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

Ας υποθέσουμε ότι έχουμε ακέραιος αριθμός παράταξη. Το πρόβλημα "Διακριτά παρακείμενα στοιχεία σε έναν πίνακα" ζητά να προσδιοριστεί εάν είναι δυνατόν να ληφθεί ο πίνακας στον οποίο όλοι οι γειτονικοί αριθμοί είναι διακριτοί ή όχι, αλλάζοντας δύο γειτονικά ή γειτονικά στοιχεία σε έναν πίνακα, εάν είναι δυνατόν, εκτυπώστε "Αλλιώς εκτυπώστε" ΟΧΙ ".

Παράδειγμα

arr[] = { 3,5,5,3,5}
YES

Σε αυτό το παράδειγμα, μπορούμε να πάρουμε τη σειρά διακριτών παρακείμενων αριθμών, αλλάζοντας τα arr [2] και arr [3] ως 5 και 2 αντίστοιχα.

Διακριτά παρακείμενα στοιχεία σε έναν πίνακα

arr[] = {3 , 5,  3, 3 }
NO

εξήγηση

Δεν μπορούμε να πάρουμε τον επιθυμητό πίνακα ακόμα και μετά την ανταλλαγή των τιμών.

Αλγόριθμος για διακριτά παρακείμενα στοιχεία σε έναν πίνακα

1. Declare a map.
2. Count and store the frequencies of each element of the array.
3. Set maxFreq to 0.
4. Get the maximum frequency of a number from the map.
5. Check if maxFreq is greater than the half-length of the array, means maxFreq >(n+1) / 2.
    1. If true, then print NO.
    2. Else print YES.

εξήγηση

Μας δίνεται ένας ακέραιος πίνακας. Μας ζητήθηκε να προσδιορίσουμε εάν έχουμε τον πίνακα στον οποίο είναι δυνατά τα ξεχωριστά παρακείμενα στοιχεία. Αυτό σημαίνει ότι εάν ένας τέτοιος πίνακας δεν είναι δυνατός, εκτυπώστε ΟΧΙ αλλιώς εκτυπώστε ΝΑΙ. Τώρα, πρέπει να ελέγξουμε πόσους αριθμούς θα ανταλλάσσονται για να πάρουμε τον επιθυμητό πίνακα. Πρέπει να ελέγξουμε την εμφάνιση κάθε στοιχείου και επίσης ότι η μέγιστη εμφάνιση δεν πρέπει να είναι μεγαλύτερη από το μισό του μήκους του πίνακα. Εάν το μήκος ενός πίνακα θα δοθεί ως 5. Εάν ένα στοιχείο έχει 3 εμφανίσεις σε έναν πίνακα. Τότε θα είναι δυνατή η αναδιάταξη του πίνακα στην πρώτη, τρίτη και πέμπτη θέση. Επομένως, θα ήταν δυνατό να αποκτήσετε ξεχωριστά παρακείμενα στοιχεία σε έναν πίνακα.

Θα κάνουμε να δηλώσουμε ένα χάρτη. Στη συνέχεια θα διασχίσουμε τον πίνακα και θα μετρήσουμε τη συχνότητα κάθε στοιχείου. Αποθηκεύστε ταυτόχρονα όλες τις συχνότητες κάθε στοιχείου σε έναν χάρτη. Ας υποθέσουμε ότι έχουμε έναν πίνακα 5 αριθμών, στον οποίο δύο από αυτούς εμφανίστηκαν δύο φορές σε έναν πίνακα και ένας άλλος αριθμός πραγματοποιήθηκε μία φορά. Έτσι θα αποθηκεύουμε τη συχνότητα κάθε στοιχείου του πίνακα. Μετά την αποθήκευση όλων των συχνοτήτων του στοιχείου. Θα ορίσουμε τη μεταβλητή maxFreq σε 0. Στην οποία πρόκειται να αποθηκεύσουμε τον μέγιστο αριθμό συχνότητας ενός στοιχείου, αφού ανακαλύψουμε τη μέγιστη συχνότητα.

Γι 'αυτό, θα διασχίζουμε τον χάρτη και θα ελέγξουμε για κάθε στοιχείο, εάν έχουμε συχνότητα μεγαλύτερη από την προηγούμενη αποθηκευμένη συχνότητα. Με αυτό, θα έχουμε τον μέγιστο αριθμό ως συχνότητα και θα ελέγξουμε εάν αυτή η συχνότητα είναι μεγαλύτερη από το μισό του μήκους του πίνακα. Εάν ισχύει, εκτυπώστε ΟΧΙ, αλλιώς εκτυπώστε ΝΑΙ.

Κώδικας

Κωδικός C ++ για Διακριτά παρακείμενα στοιχεία σε πρόβλημα πίνακα

#include<bits/stdc++.h>
using namespace std;
void areDistinctAdjacent(int a[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[a[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        if (maxFreq < MAP[a[i]])
            maxFreq = MAP[a[i]];
    if (maxFreq > (n + 1) / 2)
        cout << "NO";
    else
        cout << "YES";
}
int main()
{
    int arr[] = { 3,5,5,3,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    areDistinctAdjacent(arr, n);
    return 0;
}

 

YES

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

import java.util.HashMap;
import java.util.Map;

class adjacentDistinctElement
{
    static void areDistinctAdjacent(int a[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();

        for (int i = 0; i < n; ++i)
        {
            if(MAP.containsKey(a[i]))
            {
                int x = MAP.get(a[i]) + 1;
                MAP.put(a[i],x);
            }
            else
            {
                MAP.put(a[i],1);
            }

        }
        int maxFreq = 0;

        for (int i = 0; i < n; ++i)
            if (maxFreq < MAP.get(a[i]))
                maxFreq = MAP.get(a[i]);

        if (maxFreq > (n + 1) / 2)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
    public static void main (String[] args)
    {
        int arr[] = { 3,5,5,3,5 };
        int n = arr.length;
        areDistinctAdjacent(arr, n);
    }
}

YES

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

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

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

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Καθώς έχουμε χρησιμοποιήσει το hashmap, αποθηκεύσαμε συχνότητες στοιχείων. Και στη χειρότερη περίπτωση μπορεί να υπάρχουν όλα τα διαφορετικά στοιχεία. Τότε θα έχουμε N ζεύγη τιμών-κλειδιών. Έχουμε λοιπόν την πολυπλοκότητα του διαστήματος O (N).