Падлічыце падмасівы з аднолькавымі цотнымі і няцотнымі элементамі


Узровень складанасці Лёгка
Часта пытаюцца ў Accenture Факты Фанатыкі
масіў гашыш

Дапусцім, вы далі цэлае лік масіў памерам N. Паколькі ёсць лічбы, лічбы няцотныя і цотныя. Пастаноўка праблемы заключаецца ў падмасіве падліку з аднолькавымі цотнымі і няцотнымі элементамі альбо высвятленні колькасці падмасіваў, які мае аднолькавую колькасць цотных і няцотных цэлых лікаў.

Прыклад

уваход

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, а пазітыўNum [0] - 1.
  3. Прайсці масіў ад i = 0, да i
    1. Праверце, калі разраднасць і аперацыя arr [i] & 1 роўная 1,
      1. Калі дакладна, павялічце колькасць на 1.
    2. У адваротным выпадку паменшыце колькасць на 1.
    3. Калі колькасць менш за 0, дадайце вывад у negativNum [-count] і захавайце яго ў вывадзе.
    4. У адваротным выпадку дадайце вывад у positiveNum [count] і захавайце яго для вываду.
  4. Зваротны выхад.

Тлумачэнне

Мы зробім два хэш-масівы, адзін - для захоўвання станоўчай розніцы, а другі - для адмоўных. Мы хочам сказаць, што з розніцамі мы збіраемся высветліць адрозненні паміж частатамі няцотных і цотных лікаў. Устанавіўшы вывад на 0, мы абнавім наш адказ, падлічым да 0, гэта дазволіць падтрымліваць розніцу. Пасля абвяшчэння двух хэш-масіваў усталюйце для дадатнага 1 0, positiveNum [1] = XNUMX.

Мы пройдзем масіў і праверым, няцотнае яно ці дадатнае, для гэтага будзем выкарыстоўваць разрадны аператар І, калі выкарыстоўваем аператар І паміж 1 і любым значэннем, атрымаем два вынікі: 1 альбо 0, калі лік няцотны гэта дасць 1 як вывад, калі гэта нават тады, ён дае 0 як выхад. Калі лік апынуўся роўным 1, то мы збіраемся павялічыць лік на 1, інакш гэта можа быць толькі 0, таму мы зменшым аднолькавае значэнне ліку на 1.

Робячы гэта, мы павінны падтрымліваць наш вывад, бо, калі мы знайшлі, што значэнне count менш за 0, мы будзем складаць значэнне значэння індэкса count негатыўнага нума да вываду і павялічыць колькасць негатыўнага нума на 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

Праграма 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 (2n) дзе "П" - колькасць элементаў у масіве.