ഒരു അറേയിലെ അടുത്തുള്ള ഘടകങ്ങൾ വേർതിരിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു Coursera ഡി.ഇ.ഷാ ഉയർത്തൽ ഐബിഎം കുലിസ നാഗാരോ Opera OYO മുറികൾ Zoho
അറേ

പ്രശ്നം പ്രസ്താവന

നമുക്ക് ഒരു ഉണ്ടെന്ന് കരുതുക പൂർണ്ണസംഖ്യ ശ്രേണി. “ഒരു അറേയിലെ അടുത്തുള്ള ഘടകങ്ങൾ വേർതിരിക്കുക” എന്ന പ്രശ്‌നം, അടുത്തുള്ള എല്ലാ അക്കങ്ങളും വ്യത്യസ്‌തമായ അറേ ലഭിക്കുമോ ഇല്ലയോ എന്ന് നിർണ്ണയിക്കാൻ ആവശ്യപ്പെടുന്നു, സാധ്യമെങ്കിൽ ഒരു അറേയിൽ രണ്ട് സമീപത്തുള്ള അല്ലെങ്കിൽ അയൽ ഘടകങ്ങൾ മാറ്റിക്കൊണ്ട് “അതെ” അച്ചടിക്കുക. ”അല്ലെങ്കിൽ“ ഇല്ല ”പ്രിന്റുചെയ്യുക.

ഉദാഹരണം

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

ഈ ഉദാഹരണത്തിൽ‌, യഥാക്രമം അര [2], അറ [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.

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു പൂർണ്ണ സംഖ്യ നൽകിയിരിക്കുന്നു. വ്യത്യസ്തമായ സമീപത്തുള്ള ഘടകങ്ങൾ സാധ്യമാകുന്ന അറേ ഞങ്ങൾക്ക് ലഭിക്കുന്നുണ്ടോ എന്ന് നിർണ്ണയിക്കാൻ ഞങ്ങളോട് ആവശ്യപ്പെട്ടു. അതിനർത്ഥം അത്തരമൊരു ശ്രേണി സാധ്യമല്ലെങ്കിൽ NO പ്രിന്റുചെയ്യുക അതെ എന്ന് പ്രിന്റുചെയ്യുക. ഇപ്പോൾ, ആവശ്യമുള്ള അറേ ലഭിക്കുന്നതിന് എത്ര നമ്പറുകൾ സ്വാപ്പ് ചെയ്യണമെന്ന് ഞങ്ങൾ പരിശോധിക്കേണ്ടതുണ്ട്. ഓരോ മൂലകത്തിന്റെയും സംഭവം ഞങ്ങൾ പരിശോധിക്കേണ്ടതുണ്ട്, കൂടാതെ പരമാവധി സംഭവം അറേയുടെ നീളത്തിന്റെ പകുതിയിൽ കൂടുതലാകരുത്. ഒരു അറേയുടെ ദൈർഘ്യം 5 ആയി നൽകും. ഒരു ഘടകത്തിന് ഒരു അറേയിൽ 3 സംഭവങ്ങളുണ്ടെങ്കിൽ. ആദ്യ, മൂന്നാമത്തെയും അഞ്ചാമത്തെയും സ്ഥാനത്ത് അറേ പുന range ക്രമീകരിക്കാൻ കഴിയും. അതിനാൽ ഒരു അറേയിൽ‌ വ്യക്തമായ സമീപത്തുള്ള ഘടകങ്ങൾ‌ നേടാൻ‌ കഴിയും.

ഒരു പ്രഖ്യാപിക്കുക എന്നതാണ് ഞങ്ങൾ ചെയ്യാൻ പോകുന്നത് ഭൂപടം. തുടർന്ന് ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിച്ച് ഓരോ മൂലകത്തിന്റെയും ആവൃത്തി കണക്കാക്കും. അതോടൊപ്പം ഓരോ ഘടകത്തിന്റെയും എല്ലാ ആവൃത്തികളും ഒരു മാപ്പിൽ സംഭരിക്കുക. ഞങ്ങൾക്ക് 5 അക്കങ്ങളുടെ ഒരു ശ്രേണി ഉണ്ടെന്ന് കരുതുക, അതിൽ രണ്ടെണ്ണം ഒരു അറേയിൽ രണ്ട് തവണയും മറ്റൊരു നമ്പർ ഒരു തവണയും സംഭവിച്ചു. അതിനാൽ ഞങ്ങൾ അറേയിലെ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തി സംഭരിക്കും. മൂലകത്തിന്റെ എല്ലാ ആവൃത്തികളും സംഭരിച്ച ശേഷം. ഞങ്ങൾ മാക്സ്ഫ്രെക്ക് വേരിയബിളിനെ 0 ആയി സജ്ജീകരിക്കും, അതിൽ പരമാവധി ആവൃത്തി കണ്ടെത്തിയതിനുശേഷം ഒരു മൂലകത്തിന്റെ പരമാവധി ആവൃത്തി നമ്പർ സംഭരിക്കാൻ പോകുന്നു.

അതിനായി, മുമ്പ് സംഭരിച്ച ആവൃത്തിയേക്കാൾ വലിയ ആവൃത്തി ഉണ്ടെങ്കിൽ ഞങ്ങൾ മാപ്പിലൂടെ സഞ്ചരിക്കും, ഓരോ ഘടകങ്ങളും പരിശോധിക്കുക. ഇതുപയോഗിച്ച്, ഞങ്ങൾക്ക് ഒരു ആവൃത്തിയായി പരമാവധി എണ്ണം ഉണ്ടാകും, കൂടാതെ ആ ആവൃത്തി അറേയുടെ നീളത്തിന്റെ പകുതിയേക്കാൾ വലുതാണോ എന്ന് പരിശോധിക്കുക. ശരിയാണെങ്കിൽ, ഇല്ല എന്ന് പ്രിന്റുചെയ്യുക, അല്ലെങ്കിൽ അതെ പ്രിന്റുചെയ്യുക.

കോഡ്

ഒരു അറേ പ്രശ്‌നത്തിലെ അടുത്തുള്ള ഘടകങ്ങൾക്കായുള്ള സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ രേഖീയ സമയ സങ്കീർണ്ണത കൈവരിക്കാൻ ഞങ്ങൾക്ക് കഴിയും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ ഞങ്ങൾ ഘടകങ്ങളുടെ ആവൃത്തി സംഭരിക്കുകയായിരുന്നു. ഏറ്റവും മോശം അവസ്ഥയിൽ എല്ലാ വ്യത്യസ്ത ഘടകങ്ങളും ഉണ്ടാകാം. അപ്പോൾ നമുക്ക് N കീ-മൂല്യ ജോഡികൾ ഉണ്ടാകും. അതിനാൽ നമുക്ക് O (N) സ്പേസ് സങ്കീർണ്ണതയുണ്ട്.