በተሰጠው ክልል ዙሪያ የአንድ ድርድር ሶስት መንገድ ክፍፍል  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ባንክ ባዛር ብላክ ሮክ አቢይ አንድ ግልብጥብጥ Fab የሞንፎርግ ቤተ ሙከራዎች Synopsys ቴሊዮ ያሁ
ሰልፍ

የችግሩ መግለጫ  

አንድ ተሰጥቶሃል ደርድር of ኢንቲጀሮች እና ዝቅተኛ ዋጋ እና ከፍተኛ ዋጋ ችግሩ “በተጠቀሰው ክልል ዙሪያ የሦስት መንገድ ክፍፍል” ችግሩ እንዲደራጅ ይጠይቃል ፣ ይህ ድርድር በሦስት ክፍሎች ይከፈላል። የዝግጅት ክፍፍሎቹ-

  1. የመጀመሪያው ክፍልፋይ ንጥረ ነገሮች ከዝቅተኛ እሴት ያነሱ ይሆናሉ ፣
  2. ንጥረ ነገሮች በተጠቀሰው ክልል ውስጥ የሚገኙት ቀጣይ ክፍፍል በዚህ ክፍልፍል እና በ ውስጥ ይሆናል
  3. ከከፍተኛው እሴት የሚበልጡ ቁጥሮች የድርድሩ ሦስተኛው ክፍል ይሆናል።

ለምሳሌ  

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30
2 5 1 12 4 9 23 76 56 45 87

ማስረጃ

lowValue 15 ነው ፣ እንደዚህ በግራ በኩል ያሉት ቁጥሮች ከዝቅተኛ እሴት በታች ይሆናሉ።

ክልሉ በ 15 እና 30 መካከል ነው ፣ 23 በዚህ ክልል መካከል ያለው ቁጥር ነው

ከፍተኛ ዋጋ 30 ነው ፣ ከከፍተኛው እሴት የሚበልጡ ቁጥሮች ሁሉ በቀኝ በኩል ይሆናሉ ፡፡

በተሰጠው ክልል ዙሪያ የአንድ ድርድር ሶስት መንገድ ክፍፍል

አልጎሪዝም  

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

ማስረጃ  

ኢንቲጀር ድርድር እና የዝቅተኛ እሴት እና የከፍተኛ እሴት ክልል ሰጥተናል ፡፡ ድርድርን ማዘጋጀት ወይም ድርድርን መከፋፈል አለብን። ከዝቅተኛ እሴት በታች የሆኑ ሁሉም የድርጅት ቁጥሮች ሊኖሩ በሚችሉበት ቦታ ላይ በግራ በኩል ይገኛሉ። እና በድርድሩ ክልል መካከል ያለው ድርድር ቁጥር በድርድሩ ውስጥ ቀጥሎ ይሆናል። እና ቀጣዩ እሴቶች ከከፍተኛው እሴት የሚበልጡ ቁጥሮች የመጨረሻ ይሆናሉ ፡፡

ተመልከት
ከፍተኛ መጠን ያለው ንዑስ ክፍል ድምር እኩል ይሆናል k

ድርድሩን ከ 0 ላይ እናልፋለንth ማውጫ ወደ መጨረሻው መረጃ ጠቋሚ ፡፡ ግን ከዚያ በፊት የተወሰነ ተለዋዋጭ አውጀን በቅደም ተከተል በ 0 እና በመጨረሻው የመረጃ ጠቋሚ አማካይነት አስጀምረናል ፡፡ ከዝቅተኛ እሴት በታች ዝቅተኛ ዋጋ በተገኘ ቁጥር በማዘዋወር ክዋኔው በጅማሬው ላይ ይከናወናል እናም ከከፍተኛው እሴት በላይ የሚበልጥ እሴት በተገኘ ቁጥር ክዋኔው በማብቃት ይከናወናል ፡፡ ድርደራውን እናቋርጣለን እና የአሁኑ የድርድር ንጥረ ነገር ከተሰጠ ዝቅተኛ እሴት በታች ከሆነ እናረጋግጣለን ከዚያም የአቀማመጥ የአሁኑን እሴት እና የድርድርን የመጀመሪያ አቀማመጥ እሴት እንለውጣለን። ይህ ዋጋ የመነሻውን ነጥብ እንከታተላለን እና ሌሎች እሴቶችን ንጥረ ነገሮችን ለመለዋወጥ የማውጫ ማውጫዎችን ዱካ ይጠብቃል ፣ ኤለመንቱ አሁን ካለው የድርድር ንጥረ ነገር እሴት የሚበልጥ ሆኖ ከተገኘ ሌላ ስዋፕ ይደረጋል። ከዚያ ኤለመንቱ አሁን ካለው ንጥረ ነገር ጋር የሚቀያየርበት የማጠናቀቂያ እሴት ፣ ማውጫ ይመጣል። ከሁኔታዎች መካከል አንዳቸውም የሚያሟሉ ከሆነ ቁጥሩ በተጠቀሰው ክልል ውስጥ ይገኛል ማለት ነው ከዚያ እኛ አንለውጠውም ፡፡ ተሻጋሪው ከተጠናቀቀ በኋላ የተፈለገውን ድርድር አለን ፡፡ ድርድርን ማተም ብቻ ያስፈልገናል።

ኮድ  

በተሰጠው ክልል ዙሪያ የአንድ ድርድር ሶስት መንገድ ክፍፍልን ለመፍታት የ C ++ ኮድ

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
2 5 1 12 4 9 23 76 56 45 87

በተሰጠው ክልል ዙሪያ የአንድ ድርድር ሶስት መንገድ ክፍፍልን ለመፍታት የጃቫ ኮድ

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

        for (int i=0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");

        }
    }
}
2 5 1 12 4 9 23 76 56 45 87

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በድርድር አካላት ላይ የተሻገረን ስለሆነ የጊዜ ውስብስብነቱ መስመራዊ ነው።

ተመልከት
የድርድር Leetcode መፍትሄን በውዝ ይደምሩ

የቦታ ውስብስብነት

ኦ (1) ተጨማሪ ቦታ ስለማያስፈልግ ፡፡ አልጎሪዝም ራሱ በቦታው ላይ አልጎሪዝም ሲሆን የመጀመሪያውን የተሰጠውን ድርድር እያዘመነ ነው። ስለዚህ የአልጎሪዝም የቦታ ውስብስብነት ፕሮግራሙ መስመራዊ ሲሆን ቋሚ ነው።