การแบ่งอาร์เรย์สามวิธีรอบ ๆ ช่วงที่กำหนด  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แบงค์บาซาร์ แบล็ค ทุนหนึ่ง ป้อมปราการ Fab Moonfrog Labs Synopsys Twilio yahoo
แถว

คำชี้แจงปัญหา  

คุณจะได้รับไฟล์ แถว 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

ช่วงอยู่ระหว่าง 15 ถึง 30, 23 คือจำนวนที่อยู่ระหว่างช่วงนี้

highValue คือ 30 ตัวเลขทั้งหมดที่มากกว่า 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.

คำอธิบาย  

เราได้กำหนดอาร์เรย์จำนวนเต็มและช่วงของ lowValue และ highValue เราต้องจัดเรียงอาร์เรย์หรือแบ่งพาร์ติชันอาร์เรย์ ดังนั้นตัวเลขที่เป็นไปได้ทั้งหมดของอาร์เรย์ซึ่งน้อยกว่า lowValue จะอยู่ทางด้านซ้ายของอาร์เรย์ และจำนวนอาร์เรย์ที่อยู่ระหว่างช่วงของอาร์เรย์จะอยู่ถัดไปในอาร์เรย์ และค่าถัดไปจะเป็นตัวเลขที่มากกว่าค่า highValue จะเป็นค่าสุดท้าย

ดูสิ่งนี้ด้วย
ผลรวมซับเรย์ขนาดสูงสุดเท่ากับ k

เราจะข้ามอาร์เรย์จาก 0th ดัชนีไปยังดัชนีสุดท้าย แต่ก่อนหน้านั้นเราได้ประกาศตัวแปรและเริ่มต้นด้วย 0 และดัชนีสุดท้ายของอาร์เรย์ตามลำดับ ในการแลกเปลี่ยนเมื่อใดก็ตามที่พบค่าที่ต่ำกว่า lowValue การดำเนินการจะดำเนินการกับค่าเริ่มต้นและเมื่อใดก็ตามที่มีค่ามากกว่าค่าที่พบ highValue การดำเนินการจะดำเนินการที่ endValue เราจะสำรวจอาร์เรย์และตรวจสอบว่าองค์ประกอบอาร์เรย์ปัจจุบันน้อยกว่าค่า lowValue ที่กำหนดหรือไม่หากเป็นจริงจากนั้นสลับค่าปัจจุบันของอาร์เรย์และค่าตำแหน่งแรกของอาร์เรย์ ค่านี้เราจะติดตามจุดเริ่มต้นและค่าอื่น ๆ จะคอยติดตามดัชนีสิ้นสุดสำหรับการแลกเปลี่ยนองค์ประกอบการแลกเปลี่ยนอื่นจะทำได้หากพบองค์ประกอบมากกว่าค่าขององค์ประกอบอาร์เรย์ปัจจุบัน จากนั้นจะมีค่า endValue ซึ่งเป็นดัชนีที่องค์ประกอบถูกสลับกับองค์ประกอบปัจจุบัน หากไม่ตรงตามเงื่อนไขหมายความว่าจำนวนอยู่ในช่วงที่กำหนดเราจะไม่เปลี่ยนแปลง หลังจากการข้ามผ่านเสร็จสิ้นเรามีอาร์เรย์ที่ต้องการ เราต้องพิมพ์อาร์เรย์

รหัส  

รหัส 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) เนื่องจากไม่จำเป็นต้องมีพื้นที่เพิ่มเติม อัลกอริทึมเองเป็นอัลกอริทึมแบบแทนที่และกำลังอัปเดตอาร์เรย์ที่กำหนดเริ่มต้น ดังนั้นความซับซ้อนของพื้นที่ของอัลกอริทึมจึงคงที่ในขณะที่โปรแกรมเป็นเชิงเส้น