1 ба 0-ийн тэнцүү тооны дэд зурвасуудыг тоол


Хэцүү байдлын түвшин Easy
Байнга асуудаг Cisco КупонДуниа Coursera Өгөгдлийн сан Karat SAP лабораторууд Tesla
Array Хаш

Асуудлын мэдэгдэл

“1 ба 0-ийн тэнцүү тооны дэд зурвасуудыг тоолох” гэсэн бодлогод танд зөвхөн 0 ба 1-ээс бүрдсэн массив өгөгдсөн болно. Асуудлын шийдэл нь 0-ийн зар 1-тэй тэнцүүгүй дэд массивын тоог олохыг хүсдэг.

Жишээ нь

arr[] = {0, 0, 1, 1, 0}
4

Тайлбар: Бүх дэд массивууд (1,2), (3,4), (0,3), (1,4)

1 ба 0-ийн тэнцүү тооны дэд зурвасуудыг тоол

 

arr[] = {1,0,0,1,1,0}
7

Тайлбар: Бүх дэд массивууд нь (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5).

Алгоритм

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

Тайлбар

Бид зөвхөн 0 ба 1-ээс бүрдсэн массивыг өгсөн. Тиймээс бид зөвхөн 0 ба 1-ийг агуулсан дэд массивын тоог олох хэрэгтэй. Бид ашиглах гэж байна Хаширч байна. Бид мэдэгдэх болно газрын зураг. Газрын зураг дээр бид нийлбэр ба түүний давтамжийг 1 гэж хадгалах болно. Хэрэв энэ нь газрын зураг дээр шинэ байгаа бол газрын зурагт нэмж оруулаарай, эс тэгвэл газрын зурагт байгаа өмнөх нийлбэрийн давтамжийг нэмэгдүүл.

Гэхдээ үүнээс өмнө бид бүх 0-үүдийг -1 болгон хөрвүүлж, гогцоог дайран өнгөрөх болно. Хэрэв бид массивын элементийг 0 гэж олсон бол бид үүнийг -1 болгож хөрвүүлэх болно. Массивын одоогийн элементийн утгыг нийлбэр дээр нэмэх. Бид нийлбэрийг шалгах болно, хэрэв нийлбэр нь 0-тэй тэнцүү байвал бид гаралтын утгыг нэмэгдүүлэх болно. Учир нь бид бүх 0-ийг -1 болгож хөрвүүлж байгаа бөгөөд зөвхөн 1 ба 0-тэй байна. Тэгэхээр бид 0-ийг -1 болгож хөрвүүлээд 1-тэй тэнцүү утгыг нэмнэ. Нийлбэр 0 байх бүрт бид 0 ба 1-тэй тэнцүү үед л боломжтой болно.

Бидэнд 1 0 ба 0 1 байгаа бөгөөд 1 тус бүрийг -1 болгож хөрвүүлээд 0 0 ба 1 -0-ийг нэмбэл бид 0-ийг нийлбэр болгоно гэж бодъё. Энэ нь 1-ийг -0 болгон хөрвүүлсний дараа 0-тэй тэнцүү байхын тулд бид XNUMX ба XNUMX-тэй тэнцүү байх ёстой гэсэн үг юм. Тэгэхээр нийлбэрийн утгыг XNUMX гэж олох бүрт бид гаралтын утгыг нэмэгдүүлэх болно. Оролтын массивыг авч үзвэл бид XNUMX-ийн нийлбэрийг авах бүрт гаралтын утгыг шинэчилж байх болно.

код

1 ба 0-ийн тэнцүү тооны дэд массивуудыг тоолох C ++ код

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

1 ба 0-ийн тэнцүү тооны дэд дэд графуудыг тоолох Java код

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацаа C0 төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Бид HashMap-ийг ашигласан тул цаг хугацааны шугаман нарийн төвөгтэй байдалд хүрч чадсан.

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

O (N) хаана "N" массив дахь элементүүдийн тоо юм. HashMap дээр бид нийлбэрийг түлхүүр болгон хадгалсан тул шугаман орон зайн нарийн төвөгтэй байдалд хүрнэ.