მასივის მკაფიო მიმდებარე ელემენტები


Რთული ტური Easy
ხშირად ეკითხებიან Coursera დე შოუ ლაშქრობა IBM კულიზა ნაგარო ოპერისა OYO ოთახები Zoho
Array

პრობლემის განცხადება

დავუშვათ, რომ ჩვენ გვაქვს მთელი რიცხვი მასივი. პრობლემა ”მასივის მკაფიო მიმდებარე ელემენტები” ითხოვს იმის გარკვევას, შესაძლებელია თუ არა მასივის მიღება, რომელშიც ყველა მომიჯნავე რიცხვი განსხვავებულია თუ არა, მასივში ორი მომიჯნავე ან მეზობელი ელემენტის შეცვლით, თუ შესაძლებელია, შემდეგ დაბეჭდეთ ”დიახ” ”სხვა ბეჭდვა” არა ”.

მაგალითი

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.

განმარტება

მოცემულია მთელი მასივი. ჩვენ გვთხოვეს დავადგინოთ, მივიღებთ თუ არა მასივს, რომელშიც შესაძლებელია ცალკეული მიმდებარე ელემენტები. ეს ნიშნავს, რომ თუ ასეთი მასივი შეუძლებელია, მაშინ დაბეჭდე არაფრით დაბეჭდილი YES. ახლა ჩვენ უნდა შეამოწმოთ რამდენი რიცხვის შეცვლა ხდება სასურველი მასივის მისაღებად. ჩვენ უნდა შეამოწმოთ თითოეული ელემენტის არსებობა და ასევე, რომ მაქსიმალური მოვლენა არ უნდა იყოს მასივის სიგრძის ნახევარზე მეტი. თუ მასივის სიგრძე იქნება მოცემული როგორც 5. თუ ელემენტს აქვს 3 მოვლენა მასივში. შემდეგ შესაძლებელი იქნება მასივის გადალახვა პირველ, მესამე და მეხუთე პოზიციებზე. ასე რომ, შესაძლებელი იქნება მასივში მკაფიო მომიჯნავე ელემენტების მიღება.

ჩვენ ვაპირებთ გავაცხადოთ ა რუკა. შემდეგ ჩვენ გადავკვეთთ მასივს და დაითვლით თითოეული ელემენტის სიხშირეს. ერთდროულად შეინახეთ თითოეული ელემენტის ყველა სიხშირე რუკაზე. დავუშვათ, რომ გვაქვს 5 რიცხვის მასივი, რომელშიც ორი მათგანი ორჯერ მოხდა მასივში, ხოლო მეორე რიცხვი ერთჯერადად მოხდა. ასე რომ, ჩვენ შევნახავთ მასივის თითოეული ელემენტის სიხშირეს. ელემენტის ყველა სიხშირის შენახვის შემდეგ. ჩვენ დავაყენებთ maxFreq ცვლადს 0-ში. რომელშიც ჩვენ ვაპირებთ ელემენტის მაქსიმალური სიხშირის რაოდენობის შენახვას, მაქსიმალური სიხშირის დადგენის შემდეგ.

ამისათვის ჩვენ გადავხედავთ რუკას და გადავამოწმებთ თითოეულ ელემენტს, თუ გვაქვს წინა სიხშირეზე მეტი სიხშირე. ამით ჩვენ გვექნება მაქსიმალური რიცხვი, როგორც სიხშირე და ვამოწმებთ არის თუ არა ეს სიხშირე მასივის სიგრძის ნახევარზე მეტი. თუ სიმართლეა, მაშინ დაბეჭდე არა, წინააღმდეგ შემთხვევაში დაბეჭდე YES.

კოდი

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) სირთულე.