عد المصفوفات الفرعية بنفس العناصر الفردية والزوجية


مستوى الصعوبة سهل
كثيرا ما يطلب في اكسنتشر مجموعة الحقائق المتعصبون
مجموعة مزيج

افترض أنك أعطيت عددًا صحيحًا مجموعة بحجم N. نظرًا لوجود أرقام ، فإن الأرقام فردية أو زوجية. بيان المشكلة هو العد subarray مع نفس العناصر الزوجية والفردية أو يكتشف عدد المصفوفات الفرعية التي تحتوي على عدد متساوٍ من الأعداد الصحيحة الزوجية والفردية.

مثال

إدخال

arr [] = {2، 5، 1، 6} ؛

الناتج

3

تفسير

كما هو الحال في ⇒ {2، 5}، {1، 6}، {2، 5، 1، 6}

إدخال

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

الناتج

7

خوارزمية

  1. قم بتعريف صفيفين ، رقم موجب وسالب ، رقم بالحجم n + 1.
  2. اضبط العد والإخراج على 0 ، وعيِّن رقمًا إيجابيًا [0] على 1.
  3. اجتياز المصفوفة من أنا = 0 إلى أنا
    1. تحقق مما إذا كانت طريقة البت وأن العملية arr [i] & 1 تساوي 1 ،
      1. إذا كان هذا صحيحًا ، فقم بزيادة العد بمقدار 1.
    2. عدا ذلك ، قلل العدد بمقدار 1.
    3. إذا كان العدد أقل من 0 ، فقم بإضافة الناتج إلى Negum [-count] وتخزينه في الإخراج.
    4. عدا ذلك ، أضف الناتج إلى عدد موجب [عدد] وقم بتخزينه في الإخراج.
  4. عودة الإخراج.

تفسير

سنصنع مصففي التجزئة ، أحدهما لتخزين الفرق الإيجابي والآخر للاختلافات السلبية. نعني بالاختلافات ، أننا سنكتشف الفروق بين ترددات الأعداد الصحيحة الفردية والزوجية. ضبط الناتج على 0 ، في هذا ، سنقوم بتحديث إجابتنا ، العد إلى 0 ، وهذا سيحافظ على عدد الفرق. بعد الإعلان عن صفيفتي تجزئة ، اضبط القيمة الموجبة على 1 ، القيمة الموجبة [0] = 1.

سوف نجتاز المصفوفة ، ونتحقق مما إذا كانت قيمة فردية أم موجبة ، لذلك سنستخدم عامل Bitwise AND ، إذا استخدمنا عامل التشغيل AND بين 1 وأي قيمة ، فسنحصل على النتيجتين ، إما 1 أو 0 ، إذا ال الرقم فردي سيعطي 1 كناتج ، إذا كان حتى ذلك الحين ، فإنه يعطي 0 كناتج. إذا تم العثور على الرقم ليكون 1 ، فسنزيد العدد بمقدار 1 ، وإلا فإنه يمكن أن يكون 0 فقط ، لذلك سننقص نفس قيمة العد بمقدار 1.

أثناء القيام بذلك ، يجب أن نحافظ على ناتجنا ، لذلك إذا وجدنا أن قيمة العد أقل من 0 ، فسنضيف قيمة مؤشر عدد سالب إلى الناتج ونزيد عدد سالب نيوم بمقدار 1. عدا ذلك وجدنا فقط الرقم الأكبر من أو يساوي 0 ، لذلك سنجمع قيم مؤشر العدد الموجب إلى الناتج ونزيد عدد العدد الموجب بمقدار 1. الشيء المهم هو عندما نجد نفس القيمة لكليهما الفهرس الحالي لمصفوفات التجزئة ، فهذا يعني أننا وجدنا مصفوفة فرعية زوجية-فردية لنا. وأخيرًا ، سنعود الناتج.

تطبيق

برنامج C ++ لعدد المصفوفات الفرعية مع نفس العناصر الفردية والزوجية

#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

برنامج جافا لعدد المصفوفات الفرعية مع نفس العناصر الفردية والزوجية

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

تحليل التعقيد لعدد المصفوفات الفرعية مع نفس العناصر الفردية والزوجية

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في الصفيف.

تعقيد الفضاء

يا (2 ن) أين "ن" هو عدد العناصر في الصفيف.