ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ദില്ലി ഗ്രേ ഓറഞ്ച് ലിങ്ക്ഡ് നാഗാരോ Opera സമന്വയിപ്പിക്കുക
ഹാഷ് ലാർസൻ & ട്യൂബ്രോ ക്രമപ്പെടുത്തൽ

ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്തുക എന്ന പ്രശ്‌നം ”നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി ഒരു പ്രത്യേക ശ്രേണിയിലെ വ്യത്യസ്‌ത ഘടകങ്ങളും താഴ്ന്നതും ഉയർന്നതുമായ ശ്രേണി. ഒരു ശ്രേണിയിൽ‌ ഇല്ലാത്ത ഒരു പരിധിക്കുള്ളിൽ‌ നഷ്‌ടമായ എല്ലാ ഘടകങ്ങളും കണ്ടെത്തുക. Output ട്ട്‌പുട്ട് അടുക്കിയ ക്രമത്തിലായിരിക്കണം.

ഉദാഹരണം

ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്തുക

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

വിശദീകരണം

താഴ്ന്നതും ഉയർന്നതുമായ 1, 10 എന്നിങ്ങനെ നൽകിയിരിക്കുന്ന ശ്രേണിയിലെ അറേയിലെ നഷ്‌ടമായ അക്കങ്ങൾ ഇവയാണ്.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

വിശദീകരണം

താഴ്ന്നതും ഉയർന്നതുമായ 1, 10 എന്നിങ്ങനെ നൽകിയിരിക്കുന്ന ശ്രേണിയിലെ അറേയിലെ നഷ്‌ടമായ അക്കങ്ങൾ ഇവയാണ്.

അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഗണം.
  2. അറേയിലൂടെ സഞ്ചരിച്ച് എല്ലാ ഘടകങ്ങളും സെറ്റിലേക്ക് ഇടുക.
  3. “I” എന്നത് താഴ്ന്നതിന് തുല്യവും “i” എന്നത് ഉയർന്നതിന് തുല്യവുമാണ്.
    • ഒരു സെറ്റിൽ “i” അടങ്ങിയിട്ടില്ലെങ്കിൽ.
      • 'ഞാൻ' അച്ചടിക്കുക.

വിശദീകരണം

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

ആ ഓർഡർ ലഭിക്കുന്നതിന് ഞങ്ങൾ ഇതിനകം തന്നെ അറേ ഘടകങ്ങൾ സെറ്റിലേക്ക് സംഭരിക്കുന്നു. 'I' കുറവുള്ള ഒരു ലൂപ്പ് ഞങ്ങൾ പ്രവർത്തിപ്പിക്കേണ്ടതുണ്ട്. 'i' ന്റെ മൂല്യം ഉയർന്നതുവരെ ഞങ്ങൾ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുന്നു. സെറ്റിൽ 'i' മൂല്യം അടങ്ങിയിട്ടില്ലേ എന്ന് പരിശോധിച്ച് 'i' പ്രിന്റുചെയ്യുക. അതിനാൽ ഒരു ശ്രേണിയിൽ നിന്ന് നഷ്‌ടമായ എല്ലാ ഘടകങ്ങളും ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ ഞങ്ങൾക്ക് ലഭിക്കും. നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം.

arr [] = {2, 3, 7, 8} low = 1, high = 9

നമുക്ക് അറേയിലൂടെ സഞ്ചരിച്ച് ഒരു അറേയുടെ എല്ലാ ഘടകങ്ങളും സെറ്റിലേക്ക് ഇടേണ്ടതുണ്ട്. ഞങ്ങളുടെ സെറ്റ് ആകും

set = [2,3,7,8]

ഒരു ലൂപ്പിൽ i മുതൽ ലോ വരെ സമാരംഭിക്കുക, ലൂപ്പ് ഉയർന്നത് വരെ പ്രവർത്തിക്കുന്നു, അതിനർത്ഥം 'i' എന്നത് താഴ്ന്ന = 1 നും ഉയർന്ന = 9 നും തുല്യമാണ്

i = 1, സെറ്റിൽ i അടങ്ങിയിട്ടില്ലെങ്കിൽ, 1 പ്രിന്റുചെയ്യുന്നു

[1]

i = 2, സെറ്റിന് '2' എന്ന മൂല്യമുണ്ട്, ഒന്നും ചെയ്യുന്നില്ല.

i = 3, സെറ്റിന് '3' എന്ന മൂല്യമുണ്ട്, ഒന്നും ചെയ്യുന്നില്ല.

i = 4, സെറ്റിൽ i അടങ്ങിയിട്ടില്ലെങ്കിൽ, 4 പ്രിന്റുചെയ്യുന്നു

[1, 4]

i = 5, സെറ്റിൽ i അടങ്ങിയിട്ടില്ലെങ്കിൽ, 5 പ്രിന്റുചെയ്യുന്നു

[XXX, 1, 4]

i = 6, സെറ്റിൽ i അടങ്ങിയിട്ടില്ലെങ്കിൽ, 6 പ്രിന്റുചെയ്യുന്നു

[1, 4, 5, 6]

i = 7, സെറ്റിന് '7' എന്ന മൂല്യമുണ്ട്, ഒന്നും ചെയ്യുന്നില്ല.

i = 8, സെറ്റിന് '8' എന്ന മൂല്യമുണ്ട്, ഒന്നും ചെയ്യുന്നില്ല.

i = 9, സെറ്റിൽ i അടങ്ങിയിട്ടില്ലെങ്കിൽ, 1 പ്രിന്റുചെയ്യുന്നു

[1, 4, 5, 6, 9]

ഞങ്ങളുടെ output ട്ട്‌പുട്ട് ഇതായിരിക്കും: [1, 4, 5, 6, 9]

കോഡ്

ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

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

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

O (n + (ഉയർന്ന-താഴ്ന്ന + 1)) എവിടെ “N” അറേയിലെ നിലവിലുള്ള ഘടകങ്ങളുടെ എണ്ണം, "ഉയർന്ന" ഒപ്പം “താഴ്ന്നത്” നൽകിയ ഇൻപുട്ട് ആണ്.

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

O (n), ഏറ്റവും മോശം അവസ്ഥയിൽ, എല്ലാ ഘടകങ്ങളും വ്യത്യസ്തമാണെങ്കിൽ. ഞങ്ങൾ എല്ലാ ഘടകങ്ങളും സംഭരിക്കേണ്ടതുണ്ട്. അങ്ങനെ അൽ‌ഗോരിതം നിർമ്മിക്കുന്നതിന് രേഖീയ സമയം ആവശ്യമാണ്.