किसी सरणी में आसन्न तत्वों को विकृत करें  


कठिनाई स्तर आसान
में अक्सर पूछा Coursera डीई शॉ वृद्धि आईबीएम कुलिजा नगरो संचालित ओयो कमरे Zoho
ऐरे

समस्या का विवरण  

मान लीजिए हमारे पास ए पूर्णांक सरणी। समस्या "एक सरणी में आसन्न तत्वों" को यह निर्धारित करने के लिए कहा जाता है कि क्या यह संभव है कि उस सरणी को प्राप्त किया जा सके जिसमें सभी आसन्न संख्याएँ अलग-अलग हैं या सरणी में दो आसन्न या पड़ोसी तत्वों की अदला-बदली करने से संभव नहीं है यदि यह संभव है, तो "हाँ" को प्रिंट करें "और प्रिंट" नहीं "।

उदाहरण  

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

इस उदाहरण में, हम क्रमशः [2] और up [३] को ५ और २ के रूप में गिरफ्तार करके अलग-अलग आसन्न संख्याओं का सरणी प्राप्त कर सकते हैं।

किसी सरणी में आसन्न तत्वों को विकृत करेंपिन

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.

व्याख्या  

हमें एक पूर्णांक सरणी दी गई है। हमें यह निर्धारित करने के लिए कहा गया है कि क्या हमें वह सरणी मिलती है जिसमें आसन्न तत्व संभव हैं। इसका मतलब है कि यदि ऐसा कोई एरे संभव नहीं है, तो NO और प्रिंट YES प्रिंट करें। अब, हमें यह जांचने की आवश्यकता है कि वांछित सरणी प्राप्त करने के लिए कितने नंबर स्वैप किए जाने हैं। हमें प्रत्येक तत्व की घटना की जांच करने की आवश्यकता है और यह भी कि अधिकतम घटना सरणी की लंबाई के आधे से अधिक नहीं होनी चाहिए। यदि किसी सरणी की लंबाई 5 के रूप में दी जाएगी। फिर पहले, तीसरे और पांचवें स्थान पर सरणी को फिर से व्यवस्थित करना संभव होगा। इसलिए एक सरणी में अलग-अलग आसन्न तत्वों को प्राप्त करना संभव होगा।

यह भी देखें
रैखिक समय में आकार 3 के एक क्रमबद्ध बाद का पता लगाएं

हम एक घोषणा करने जा रहे हैं नक्शा। फिर हम सरणी को पार करेंगे और प्रत्येक तत्व की आवृत्ति की गणना करेंगे। इसके साथ ही प्रत्येक तत्व की सभी आवृत्तियों को मानचित्र में संगृहीत करें। मान लीजिए हमारे पास 5 संख्याओं की एक सरणी है, जिसमें उनमें से दो एक सरणी में दो बार और दूसरी संख्या एक बार हुई। तो हम सरणी के प्रत्येक तत्व की आवृत्ति को संग्रहीत करेंगे। तत्व की सभी आवृत्तियों को संग्रहीत करने के बाद। हम अधिकतम आवृत्ति चर को 0. पर सेट करेंगे। जिसमें हम अधिकतम आवृत्ति का पता लगाने के बाद एक तत्व की अधिकतम आवृत्ति संख्या को स्टोर करने जा रहे हैं।

उसके लिए, हम नक्शे को ट्रेस करेंगे, और प्रत्येक तत्व की जांच करेंगे, अगर हमारे पास पहले से संग्रहीत आवृत्ति से अधिक आवृत्ति है। इसके साथ, हमारे पास एक आवृत्ति के रूप में अधिकतम संख्या होगी, और जांचें कि क्या यह आवृत्ति सरणी की लंबाई के आधे से अधिक है। यदि सही है, तो NO को प्रिंट करें, अन्यथा 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

किसी सरणी समस्या में आसन्न तत्वों के लिए जावा कोड

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

जटिलता विश्लेषण  

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। क्योंकि हमने हाशमैप का उपयोग किया है इसलिए हम रैखिक समय की जटिलता को प्राप्त करने में सक्षम हैं।

यह भी देखें
पुनरावृत्त पूर्व-आदेश ट्रैवर्सल

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। जैसा कि हमने हैशमैप का उपयोग किया है हम तत्वों की आवृत्तियों का भंडारण कर रहे थे। और सबसे खराब स्थिति में सभी अलग-अलग तत्व हो सकते हैं। फिर हमारे पास एन कुंजी-मूल्य जोड़े होंगे। इसलिए हमारे पास O (N) स्पेस की जटिलता है।