Subarray ที่ยาวที่สุดมีจำนวน 1s มากกว่า Count of 0s


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ อเมซอน เดอชอว์ ซัมซุง
แถว กัญชา

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

ตัวอย่าง

Input:

arr [] = {1,0,1,1,0,0,0}

Output:

5

คำอธิบาย:

ตั้งแต่ 0 ถึง 4 ดัชนี {1, 0, 1, 1, 0} มีสามตัว 1 และ 0 สอง. เพียงแค่นับ 1 มากกว่า 0 เท่านั้น

Input:

arr [] = {1,0,1,0,0}

Output:

3

คำอธิบาย:

จากดัชนี 0 ถึง 2, {1, 0, 1} มี 1 สองตัวและหนึ่ง 0 เพียงแค่นับ 1 มากกว่า 0 เท่านั้น

ขั้นตอนวิธี

  1. ประกาศแผนที่
  2. ตั้งค่า sum และ outputLength เป็น 0
  3. สำรวจอาร์เรย์ในขณะที่ i = 0 ถึง i <n
    1. ตรวจสอบว่า arr [i] เท่ากับ 0 ถ้าเป็นจริงแล้วบวก -1 เข้าไปในผลรวม
    2. มิฉะนั้นให้เพิ่ม +1 ลงในผลรวม
    3. ตรวจสอบว่า ผลรวมเท่ากัน เป็น 1 จากนั้นเพิ่มค่าของ outputLength ขึ้น 1
    4. ตรวจสอบว่าแผนที่ไม่มีผลรวมหรือไม่ถ้าเป็นจริงจากนั้นใส่ผลรวมและค่าปัจจุบันของ i ลงในแผนที่พร้อมกับผลรวม
    5. ตรวจสอบว่าแผนที่มี (sum-1) หรือไม่
    6. ถ้า outputLength น้อยกว่า i-index (ค่าของ sum ในแผนที่)
      1. ถ้าเป็นจริงให้อัพเดต outputLength เป็น i-index
  4. ส่งกลับความยาวเอาต์พุต

คำอธิบาย

เราจะประกาศก แผนที่. ในแผนที่นั้นเราจะจัดเก็บค่าของผลรวมและมูลค่าปัจจุบันของดัชนีหากเงื่อนไขเป็นไปตามนั้น ใช้สองตัวแปรและกำหนด sum เป็น 0 และ outputLength เป็น 0 ในขณะที่ข้ามอาร์เรย์เราจะเลือกแต่ละองค์ประกอบของอาร์เรย์และตรวจสอบว่า arr [i] เท่ากับ 0 หรือไม่หากพบว่าเท่ากันเราจะเพิ่ม -1 เพื่อหาผลรวมและเก็บไว้เป็นผลรวมมิฉะนั้นหากเราไม่พบว่าเป็น 0 เราจะเพิ่ม 1 บวกเพื่อรวมและเก็บไว้เพื่อรวม

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

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

การดำเนินงาน

โปรแกรม C ++ สำหรับ Subarray ที่ยาวที่สุดมี Count of 1s มากกว่า Count of 0s

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

โปรแกรม Java สำหรับ Subarray ที่ยาวที่สุดมีจำนวน 1s มากกว่า Count of 0s

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

การวิเคราะห์ความซับซ้อนสำหรับ Subarray ที่ยาวที่สุดที่มีจำนวน 1s มากกว่า Count of 0s

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

O (n) ที่ไหน “ n”  คือจำนวนองค์ประกอบในอาร์เรย์

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

O (n) ที่ไหน “ n”  คือจำนวนองค์ประกอบในอาร์เรย์