Массивыг өгөгдсөн мужид хуваах гурван арга  


Хэцүү байдлын түвшин Easy
Байнга асуудаг BankBazaar БлэкРок Капитал Нэг Citadel Fab Moonfrog лабораторууд Синопсис Twilio Yahoo
Array

Асуудлын мэдэгдэл  

Танд массив of бүхэл тоо lowValue ба highValue гэсэн утгатай. "Өгөгдсөн мужийг тойрсон массивыг гурван талт хуваалт" гэсэн асуудал массивыг гурван хэсэгт хуваах массивыг хуваахыг хүсдэг. Массивын хуваалт нь:

  1. Эхний хуваалтын элементүүд нь lowValue-ээс бага байх болно,
  2. Элементүүд өгөгдсөн хязгаарт багтах дараагийн хуваалт нь энэ хуваалт ба
  3. HighValue-ээс их тоо нь массивын гуравдахь хуваалт байх болно.

Жишээ нь  

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, зүүн талын тоо нь lowValue-ээс бага байх тул XNUMX байна.

Энэ муж нь 15-аас 30-ийн хооронд, 23 нь энэ хүрээний хоорондох тоо юм

highValue нь 30, highValue-ээс их бүх тоо баруун талд байх болно.

Массивыг өгөгдсөн мужид хуваах гурван аргаPin

Алгоритм  

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.

Тайлбар  

Бид бүхэл тоон массив ба lowValue ба highValue мужийг өгсөн. Бид массивыг хуваах эсвэл хуваах ёстой. Массивын lowValue-ээс бага бүх боломжит тоо массивын зүүн талд байх болно. Массивын хоорондох массивын тоо массивын дараа байх болно. Дараагийн утга нь highValue-ээс их тоо нь хамгийн сүүлд байх болно.

мөн үзнэ үү
Хамгийн дээд хэмжээ нь дэд массивын нийлбэр нь k-тэй тэнцүү байна

Бид 0-ээс массивыг дайран өнгөрөх болноth сүүлийн индекс рүү индекс. Гэхдээ үүнээс өмнө бид зарим хувьсагчийг зарлаж, массивын 0 ба сүүлчийн индексээр эхлүүлнэ. LowValue-ээс доогуур утга олдох бүрт үйлдлийг startValue дээр, харин highValue-ээс их утга олдох үед үйлдлийг endValue-д гүйцэтгэх болно. Бид массивыг дайран өнгөрч, массивын одоогийн элемент өгөгдсөн lowValue-ээс бага эсэхийг шалгаад массивын одоогийн утга ба массивын эхний байрлалын утгыг солино. Энэ утга нь бид эхлэх цэгийг хянах бөгөөд бусад утга нь элементүүдийг солих төгсгөлийн индексийг хянах бөгөөд элемент нь одоогийн массивын элементийн утгаас их байвал өөр своп хийх болно. Дараа нь endingValue гэсэн индекс гарч ирэхэд тухайн элементийг одоогийн элементтэй сольж тавьдаг. Хэрэв нөхцөл байдлын аль нь ч хангагдаагүй бол тухайн тоо нь тухайн хязгаарт багтана гэсэн үг бол бид үүнийг өөрчлөхгүй. Товчлол дууссаны дараа бид хүссэн массивтай болно. Бид зөвхөн массивыг хэвлэх хэрэгтэй.

код  

Шийдвэрлэх 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

Шийдвэрлэх Java код. Өгөгдсөн муж дахь массивыг гурван аргаар хуваах

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

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид массивын элементүүдийг туулсан тул цаг хугацааны нарийн төвөгтэй байдал нь шугаман байна.

мөн үзнэ үү
Array Leetcode шийдлийг холино

Сансрын нарийн төвөгтэй байдал

O (1) нэмэлт зай шаардагдахгүй тул. Алгоритм нь өөрөө алгоритм бөгөөд эхний өгөгдсөн массивыг шинэчилж байна. Тиймээс програм нь шугаман байх үед алгоритмын орон зайн нарийн төвөгтэй байдал тогтмол байдаг.