计算具有相同偶数和奇数元素的子数组


难度级别 易得奖学金
经常问 Accenture 事实集 狂徒
排列 哈希

假设您给了一个整数 排列 N大小。 因为有数字,所以数字是奇数或偶数。 问题陈述是具有相同偶数和奇数元素的count子数组,或者找出具有相等数量的偶数和奇数整数的子数组的计数。

使用案列

输入

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

输出

3

说明

因为有⇒{2,5},{1,6},{2,5,1,6}

输入

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

输出

7

算法

  1. 声明两个数组,大小为n + 1的positiveNum和negativeNum。
  2. 将count和output设置为0,并将positiveNum [0]设置为1。
  3. 遍历数组 从i = 0到i
    1. 检查按位和运算arr [i]&1是否等于1,
      1. 如果为true,则将计数增加1。
    2. 否则,将计数减少1。
    3. 如果计数小于0,则将输出添加到negativeNum [-count]并将其存储到输出。
    4. 否则,将输出添加到positiveNum [count]并将其存储到输出。
  4. 返回输出。

说明

我们将创建两个哈希数组,一个用于存储正差,一个用于负差。 有了差异,我们要说的是,我们将找出奇数和偶数整数频率之间的差异。 将输出设置为0,在此,我们将更新我们的答案,计数为0,这将保持差值计数。 声明两个哈希数组后,将正数1设置为0,positiveNum [1] = XNUMX。

我们将遍历数组,并检查它是一个奇数还是正数,为此,我们将使用按位AND运算符,如果在1到任意值之间使用AND运算符,则将得到两个结果,即1或0,如果这 数字是奇数 它会给出1作为输出,即使是,它也会给出0作为输出。 如果发现数字为1,那么我们将把计数增加1,否则只能增加0,所以我们将相同的计数值减少1。

这样做时,我们应该保持输出,因为如果发现count的值小于0,则将负Num计数的索引值加到输出中,并将negativeNum的计数增加1。否则我们只会发现大于或等于0的数字,因此我们将positiveNum计数的索引值添加到输出中,并将positiveNum的计数增加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

具有相同偶数和奇数元素的Count子数组的Java程序

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(N) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(2n) 哪里 “ n” 是数组中元素的数量。