ការបែងចែកបីវិធីនៃអារេជុំវិញជួរដែលបានផ្តល់


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ បេប៊ីបាហ្សា BlackRock សាលាមួយ Citadel Fab មន្ទីរពិសោធន៍ Moonfrog Synopsys Twilio ក្រុមហ៊ុន Yahoo
អារេ

សេចក្តីថ្លែងការណ៍បញ្ហា។

អ្នកត្រូវបានផ្តល់ឱ្យ អារេ 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

ការពន្យល់

តម្លៃទាបគឺ ១៥ ដែលលេខនៅខាងឆ្វេងនឹងតិចជាងតម្លៃទាប។

ជួរស្ថិតនៅចន្លោះពី ១៥ ទៅ ៣០, ២៣ គឺជាលេខដែលស្ថិតនៅចន្លោះជួរនេះ

HighValue គឺ ៣០ រាល់លេខទាំងអស់ដែលខ្ពស់ជាង HighValue នឹងស្ថិតនៅផ្នែកខាងស្តាំ។

ការបែងចែកបីវិធីនៃអារេជុំវិញជួរដែលបានផ្តល់

ក្បួនដោះស្រាយ

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.

ការពន្យល់

យើងបានផ្តល់អារេចំនួនគត់និងជួរនៃតម្លៃទាបនិងខ្ពស់។ យើងត្រូវរៀបចំអារេឬចែកភាគថាស។ ដូចថារាល់ចំនួនដែលអាចធ្វើបាននៃអារេដែលទាបជាងវ៉ាលែននឹងស្ថិតនៅខាងឆ្វេងនៃអារេ។ ហើយចំនួនអារេដែលស្ថិតនៅចន្លោះជួរអារេនឹងនៅជាប់នឹងជួរអារេ។ ហើយតម្លៃបន្ទាប់នឹងជាលេខដែលធំជាងលេខខ្ពស់នឹងជាលេខចុងក្រោយ។

យើងនឹងឆ្លងកាត់អារេពីលេខ ០th លិបិក្រមទៅសន្ទស្សន៍ចុងក្រោយ។ ប៉ុន្តែមុននោះយើងបានប្រកាសអថេរខ្លះហើយចាប់ផ្តើមវាជាមួយលេខ ០ និងសន្ទស្សន៍ចុងក្រោយនៃអារេរៀងៗខ្លួន។ ក្នុងការប្តូរតម្លៃរាល់ពេលដែលតម្លៃទាបជាងតម្លៃទាបត្រូវបានរកឃើញប្រតិបត្ដិការនឹងត្រូវបានអនុវត្តនៅលើតម្លៃចាប់ផ្តើមហើយរាល់ពេលដែលតម្លៃខ្ពស់ជាងតម្លៃខ្ពស់ដែលបានរកឃើញនោះប្រតិបត្តិការនឹងត្រូវបានអនុវត្តនៅចុងបញ្ចប់វ៉ាឡាំង។ យើងនឹងឆ្លងកាត់អារេហើយពិនិត្យមើលថាតើធាតុអារេបច្ចុប្បន្នទាបជាងតម្លៃទាបដែលបានផ្តល់ប្រសិនបើពិតបន្ទាប់មកប្តូរតម្លៃបច្ចុប្បន្ននៃអារេនិងតម្លៃទីតាំងដំបូងរបស់អារេ។ តម្លៃនេះយើងនឹងតាមដានចំណុចចាប់ផ្តើមហើយតម្លៃផ្សេងទៀតនឹងរក្សាដាននៃសន្ទស្សន៍បញ្ចប់សម្រាប់ប្តូរធាតុការផ្លាស់ប្តូរមួយទៀតនឹងត្រូវធ្វើឡើងប្រសិនបើរកឃើញធាតុធំជាងតម្លៃនៃធាតុអារេបច្ចុប្បន្ន។ បន្ទាប់មកភ្ជាប់មកចុងបញ្ចប់នៃលិបិក្រមដែលធាតុត្រូវបានផ្លាស់ប្តូរជាមួយធាតុបច្ចុប្បន្ន។ ប្រសិនបើគ្មានលក្ខខណ្ឌណាមួយដែលពេញចិត្តមានន័យថាលេខស្ថិតនៅក្នុងជួរដែលបានផ្តល់នោះយើងមិនផ្លាស់ប្តូរវាទេ។ បន្ទាប់ពីការឆ្លងកាត់បញ្ចប់យើងមានអារេដែលចង់បាន។ យើងគ្រាន់តែត្រូវការបោះពុម្ពអារេ។

លេខកូដ

កូដ 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” គឺជាចំនួនធាតុក្នុងអារេ។ ចាប់តាំងពីយើងបានឆ្លងកាត់ធាតុអារេភាពស្មុគស្មាញពេលវេលាគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដោយមិនចាំបាច់មានទំហំបន្ថែម។ ក្បួនដោះស្រាយដោយខ្លួនវាគឺនៅនឹងកន្លែងដោះស្រាយហើយកំពុងធ្វើបច្ចុប្បន្នភាពអារេដែលបានផ្តល់ដំបូង។ ដូច្នេះភាពស្មុគស្មាញចន្លោះនៃក្បួនដោះស្រាយគឺថេរខណៈពេលដែលកម្មវិធីគឺលីនេអ៊ែរ។