የአንድ ክልል የጎደሉ አባሎችን ያግኙ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አቅርቦት ግሬይ ብርቱካናማ LinkedIn ናጋሮ ኦፔራ Synopsys
ሃሽ ላርሰን እና ቶብሮ መደርደር

ችግሩ የክልል የጎደሉ አካላትን ፈልግ ”ይላል አንድ ደርድር በአንድ የተወሰነ ክልል ውስጥ ያሉ ልዩ አካላት እና እንደ ዝቅተኛ እና ከፍተኛ የተሰጠው ክልል። ሁሉንም የጎደሉ አባሎች በድርድር ውስጥ በማይገኝ ክልል ውስጥ ይፈልጉ። ውጤቱ በተስተካከለ ቅደም ተከተል መሆን አለበት።

ለምሳሌ  

የአንድ ክልል የጎደሉ አባሎችን ያግኙጭንቅላታም መያያዣ መርፌ

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› ን ያትሙ ፡፡ ስለሆነም ከድርድር የጎደሉ ነገሮችን በሙሉ በተወሰነ ክልል ውስጥ እናገኛለን። እስቲ አንድ ምሳሌ እንመልከት።

arr [] = {2, 3, 7, 8} ዝቅተኛ = 1 ፣ ከፍተኛ = 9

ድርድርን ማለፍ እና የአንድ ድርድርን ሁሉንም ንጥረ ነገሮች ወደ ስብስቡ ውስጥ ማስገባት ያስፈልገናል። የእኛ ስብስብ ይሆናል

አዘጋጅ = [2,3,7,8]

በክብ ውስጥ i ን ወደ ዝቅተኛ እና ዑደት እስከ ከፍተኛ ድረስ ያካሂዳል ፣ ይህ ማለት “i” ከዝቅተኛ = 1 እና ከፍተኛ = 9 ጋር እኩል ነው ማለት ነው

i = 1 ፣ ስብስቡ እኔ ከሌለው ፣ 1 ን ያትማል

[1]

i = 2 ፣ ስብስብ ‘2’ እሴት አለው እና ምንም አያደርግም።

i = 3 ፣ ስብስብ ‘3’ እሴት አለው እና ምንም አያደርግም።

i = 4 ፣ ስብስቡ እኔ ከሌለው ፣ 4 ን ያትማል

[1, 4]

i = 5 ፣ ስብስቡ እኔ ከሌለው ፣ 5 ን ያትማል

[1, 4, 5]

i = 6 ፣ ስብስቡ እኔ ከሌለው ፣ 6 ን ያትማል

[1, 4, 5, 6]

i = 7 ፣ ስብስብ ‘7’ እሴት አለው እና ምንም አያደርግም።

i = 8 ፣ ስብስብ ‘8’ እሴት አለው እና ምንም አያደርግም።

i = 9 ፣ ስብስቡ እኔ ከሌለው ፣ 1 ን ያትማል

[1, 4, 5, 6, 9]

የእኛ ውጤት ይሆናል: [1, 4, 5, 6, 9]

ኮድ  

የአንድ ክልል የጎደሉ አባሎችን ለማግኘት የ C ++ ኮድ

#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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (n + (ከፍተኛ-ዝቅተኛ + 1)) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ፣ “ከፍተኛ” ና “ዝቅተኛ” የቀረበው ግብዓት ነው

ተመልከት
ከሚዛመዱ ንጥረ ነገሮች ጋር ትልቁን ንዑስ ክፍል ርዝመት

የቦታ ውስብስብነት

ኦ (n) ፣ በጣም መጥፎ በሆነ ሁኔታ ፣ ሁሉም ንጥረ ነገሮች የተለዩ ከሆኑ። ሁሉንም ንጥረ ነገሮች ማከማቸት አለብን። ስለዚህ ስልተ ቀመሩን መስመራዊ ጊዜ ይፈልጋል።