subarray ที่ใหญ่ที่สุดโดยมีจำนวน 0 และ 1 เท่ากัน


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน Coursera สีเทาOrange MakeMyTrip สแตนลี่ย์มอร์แกน Paytm Synopsys ไทม์อินเทอร์เน็ต
แถว กัญชา

คุณได้รับอาร์เรย์ของจำนวนเต็ม จำนวนเต็มเป็นเพียง 0 และ 1 ในอาร์เรย์อินพุต คำสั่งปัญหาขอให้ค้นหาอาร์เรย์ย่อยที่ใหญ่ที่สุดที่สามารถมีจำนวนเท่ากับ 0 และ 1 ได้

ตัวอย่าง

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

คำอธิบาย

จากตำแหน่งอาร์เรย์ 0 ถึง 5 ไม่มีค่าเท่ากับ 0 และ 1

0s นับ 3

1s นับ ⇒ 3

และนี่คืออาร์เรย์ย่อยที่ใหญ่ที่สุดที่มี 0s และ 1s เท่ากัน

อัลกอริทึมเพื่อค้นหา subarray ที่ใหญ่ที่สุดโดยมีจำนวน 0 และ 1 เท่ากัน

  1. ประกาศก HashMap.
  2. ชุด รวม, maxLength, startIndex ถึงปี 0 และ endIndex ถึง -1.
  3. สำรวจอาร์เรย์และอัปเดตแต่ละองค์ประกอบของอาร์เรย์เป็น -1 หากมีค่าเท่ากับ 0
  4. เริ่มลูปจาก 0 ถึง n-1 (n คือความยาวของอาร์เรย์)
    1. เพิ่มแต่ละค่าของ arr [i] เพื่อรวม
    2. ตรวจสอบว่าผลรวมเท่ากับ 0 หรือไม่ถ้าเป็นจริง
      1. จากนั้นอัปเดต maxLength เป็น i + 1 และ endIndex เป็นฉัน.
    3. ตรวจสอบว่าแผนที่มีผลรวม + n อยู่หรือไม่
      1. จากนั้นอัปเดตความยาวของ maxLength เป็นค่า i - map (sum + n) จากแผนที่และ endIndex เป็น i
    4. อื่นใส่ sum + n ลงในแผนที่
  5. พิมพ์ endIndex - maxLength + 1 และ endingIndex

คำอธิบาย

เมื่อได้รับอาร์เรย์และเราจะขอให้ค้นหาอาร์เรย์ย่อยที่ใหญ่ที่สุดที่มีจำนวน 0 และ 1 เท่ากัน ค้นหาช่วงของอาร์เรย์ย่อยเพื่อให้มีขนาดใหญ่ที่สุดในบรรดาความยาวทั้งหมดของอาร์เรย์ย่อยทั้งหมดซึ่งมีจำนวน 0 และ 1 เท่ากัน เราจะใช้ไฟล์ HashMap สำหรับการจัดเก็บไฟล์ จำนวนเต็ม ค่าในนั้น hashing ให้แนวทางที่มีประสิทธิภาพและความซับซ้อนของเวลาที่ดีขึ้น รับค่า รวม, maxLength เป็น 0 จากนั้นเราจะอัปเดตพร้อมกันในโค้ด เราจะมีตัวแปรหนึ่งตัวที่เรียกว่า endIndex ซึ่งจะเก็บค่าของจุดสุดท้ายของช่วงที่ควรเป็นความยาวสูงสุดของช่วงของอาร์เรย์ย่อยสิ้นสุด

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

เรากำลังจะสรุปทุกค่าในอาร์เรย์และค้นหาว่ามันเท่ากับ 0 หรือไม่ถ้าเท่ากันเพียงแค่อัปเดต maxLength ของอาร์เรย์และ endIndex ของอาร์เรย์ เราจะใส่ sum + n ลงในแผนที่หากยังไม่มีอยู่และหากมีอยู่ให้ตรวจสอบเงื่อนไขบางอย่างจากนั้นอัปเดตค่า maxLength และ endIndex พิมพ์ endIndex - maxLength + 1 เป็นจุดเริ่มต้นของช่วงและ endIndex เป็นจุดสิ้นสุดของช่วง

subarray ที่ใหญ่ที่สุดโดยมีจำนวน 0 และ 1 เท่ากัน

รหัส

รหัส C ++ เพื่อค้นหา subarray ที่ใหญ่ที่สุดโดยมีจำนวน 0s และ 1s เท่ากัน

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

การนำไปใช้งานใน Java เพื่อค้นหา subarray ที่ใหญ่ที่สุดโดยมีจำนวน 0 และ 1 เท่ากัน

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ ที่นี่เราสามารถแก้ปัญหานี้ได้ใน O (n) เนื่องจากเราใช้ HashMap เนื่องจาก HashMap สามารถแทรกลบหรือแก้ไของค์ประกอบในความซับซ้อนของเวลา O (1) ได้

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากจำนวนองค์ประกอบที่จะถูกแทรกในกรณีที่เลวร้ายที่สุดในแฮชแมปจะอยู่ที่ n มากที่สุด ความซับซ้อนของปริภูมิเชิงเส้นนี้ทำได้