นับ Subarrays ที่มีองค์ประกอบคู่และคี่เหมือนกัน  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ ข้อเท็จจริง fanatics
แถว กัญชา

สมมติว่าคุณให้จำนวนเต็ม แถว ขนาด N เนื่องจากมีตัวเลขจำนวนจึงเป็นเลขคี่หรือคู่ คำสั่งปัญหาคือ count subarray ที่มีองค์ประกอบคู่และคี่เหมือนกันหรือค้นหาจำนวนอาร์เรย์ย่อยที่มีจำนวนเต็มคู่และจำนวนคี่เท่ากัน

ตัวอย่าง  

อินพุต

arr [] = {2, 5, 1, 6};

เอาท์พุต

3

คำอธิบาย

ตามที่มี⇒ {2, 5}, {1, 6}, {2, 5, 1, 6}

อินพุต

arr [] = {2,3,4,5,1,6}

เอาท์พุต

7

ขั้นตอนวิธี  

  1. ประกาศสองอาร์เรย์คือ positiveNum และ negativeNum ของขนาด n + 1
  2. ตั้งค่าจำนวนและเอาต์พุตเป็น 0 และตั้งค่า positiveNum [0] เป็น 1
  3. สำรวจอาร์เรย์ จาก i = 0 ถึง i
    1. ตรวจสอบว่า bitwise และ operation arr [i] & 1 เท่ากับ 1 หรือไม่
      1. ถ้าเป็นจริงให้เพิ่มการนับ 1
    2. มิฉะนั้นให้ลดจำนวนลง 1
    3. ถ้าจำนวนน้อยกว่า 0 ให้เพิ่มเอาต์พุตเป็น negativeNum [-count] และเก็บไว้ในเอาต์พุต
    4. มิฉะนั้นให้เพิ่มเอาต์พุตเป็น positiveNum [count] และเก็บไว้ในเอาต์พุต
  4. ส่งคืนเอาต์พุต

คำอธิบาย  

เราจะสร้างแฮชอาร์เรย์สองอาร์เรย์หนึ่งอาร์เรย์สำหรับเก็บความแตกต่างเชิงบวกและอีกอันสำหรับความแตกต่างเชิงลบ ด้วยความแตกต่างเราหมายถึงว่าเราจะหาความแตกต่างระหว่างความถี่ของจำนวนเต็มคี่และจำนวนเต็ม การตั้งค่าผลลัพธ์เป็น 0 ในนี้เราจะอัปเดตคำตอบของเรานับเป็น 0 สิ่งนี้จะรักษาการนับผลต่าง หลังจากประกาศแฮชอาร์เรย์สองอาร์เรย์แล้วให้ตั้งค่า 1 ค่าบวกเป็น 0 ค่าบวก [1] = XNUMX

ดูสิ่งนี้ด้วย
ลดความแตกต่างสูงสุดระหว่างความสูง

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

ในขณะที่ทำสิ่งนี้เราควรรักษาผลลัพธ์ของเราไว้เพราะถ้าเราพบว่าค่าของ count มีค่าน้อยกว่า 0 เราจะเพิ่มมูลค่าของค่าดัชนีของจำนวน negativeNum ให้กับเอาต์พุตและเพิ่มจำนวน negativeNum ขึ้น 1 อย่างอื่น เราพบเพียงจำนวนที่มากกว่าหรือเท่ากับ 0 ดังนั้นเราจะเพิ่มค่าของดัชนีจำนวน positiveNum ให้กับผลลัพธ์และเพิ่มจำนวน positiveNum ขึ้น 1 สิ่งที่สำคัญคือเมื่อใดก็ตามที่เราพบค่าเดียวกันของทั้งสอง ดัชนีปัจจุบันของแฮชอาร์เรย์หมายความว่าเราพบอาร์เรย์ย่อยคู่ - คี่สำหรับเรา และในที่สุดเราจะส่งคืนผลลัพธ์

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

โปรแกรม C ++ สำหรับ Count Subarrays ที่มีองค์ประกอบคู่เดียวกันและคี่

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

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

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}
Even Odd Sub-Arrays are: 7

โปรแกรม Java สำหรับ Count Subarrays ที่มีองค์ประกอบคู่และคี่เหมือนกัน

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

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

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}
Even Odd Sub-Arrays are: 7

การวิเคราะห์ความซับซ้อนสำหรับการนับ Subarrays ที่มีองค์ประกอบคู่และคี่เหมือนกัน  

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

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

ดูสิ่งนี้ด้วย
การแบ่งอาร์เรย์ออกเป็นคู่ด้วยผลรวมหารด้วย K

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

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