Ижил тэгш, сондгой элемент бүхий дэд хураамжийг тоол


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accenture Factset Фанатикууд
Array Хаш

Та бүхэл тоо өгсөн гэж бодъё массив N хэмжээтэй. Тоонууд байгаа тул тоонууд нь сондгой, тэгш тоотой байна. Асуудлын өгүүлбэр нь ижил тэгш, сондгой элементтэй дэд дэд массивыг тоолох буюу тэгш, сондгой бүхэл тоотой тэнцүү дэд массивын тоог олох болно.

Жишээ нь

Оролт

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 хэмжээтэй эерэгNum ба хасахNum гэсэн хоёр массивыг зарлана уу.
  2. Тооцоолол ба гаралтыг 0 болгож, позитивNum [0] -ыг 1 болгож тохируулна уу.
  3. Массивыг тойрон гарах i = 0-ээс i хүртэл
    1. Браузер ба arr [i] & 1 ажиллагаа нь 1-тэй тэнцүү байгаа эсэхийг шалгана,
      1. Хэрэв үнэн бол тооллыг 1-ээр нэмэгдүүлэх хэрэгтэй.
    2. Бусад тохиолдолд тооллогыг 1-р бууруул.
    3. Хэрэв тоо 0-ээс бага бол гаралтыг сөрөгNum [-count] дээр нэмээд гарахад хадгална.
    4. Бусад тохиолдолд, гаралтыг позитивNum [count] дээр нэмээд гаралтанд хадгална.
  4. Гаралтыг буцаах.

Тайлбар

Бид хоёр хэш массивыг нэгийг нь эерэг, нөгөө нь сөрөг ялгааг хадгалах зорилгоор хийх болно. Ялгаатай бол сондгой, тэгш бүхэл тоонуудын давтамжийн ялгааг олж мэдье гэж хэлмээр байна. Гаралтыг 0 болгож, бид хариултаа шинэчилж, 0 болгоно, ингэснээр ялгааны тоог хадгалах болно. Хоёр хэш массивыг зарласны дараа эерэгийг 1 болгож, позитивNum [0] = 1 болго.

Бид массивыг дайран өнгөрч, сондгой эсвэл эерэг утгатай эсэхийг шалгана, ингэснээр Bitwise AND операторыг ашиглана, AND операторыг 1-ээс ямар ч утгын хооронд ашиглавал 1 буюу 0 гэсэн хоёр үр дүнг авна. The тоо сондгой байна энэ нь 1-ийг гаралт болгоно, хэрэв тэгвэл 0-ийг гаралт болгоно. Хэрэв энэ тоо 1 байвал бид тоог 1-ээр нэмэгдүүлэх болно, тэгэхгүй бол зөвхөн 0 болно, тиймээс бид ижил тооллын утгыг 1-ээр бууруулна.

Үүнийг хийхийн тулд бид гаралтаа хадгалах ёстой, учир нь хэрэв тооллын утга 0-ээс бага байвал бид гаралт дээр сөрөгNum тооллын индексийн утгыг нэмж, сөрөгNum-ийн тоог 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 (N) хаана "N" массив дахь элементүүдийн тоо юм.

Сансрын нарийн төвөгтэй байдал

O (2n) хаана "N" массив дахь элементүүдийн тоо юм.