ספרו מערכי משנה עם מספר שווה של 1 ו- 0


רמת קושי קַל
נשאל לעתים קרובות סיסקו קופון דוניה Coursera דאטבריקס קראט מעבדות SAP טסלה
מערך בליל

הצהרת בעיה

הבעיה "ספירת מערכי משנה עם מספר שווה של 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 ומוסיפים את הערך עם 1s. בכל פעם שהסכום הוא 0 זה אפשרי רק כשיש לנו 0 ו -1.

נניח שיש לנו שלוש 1 ושלוש 0, והמרה של כל 0 ל -1 והוספת שלושת 1 ושלוש -1, יהיה לנו 0 כסכום. זה גם מרמז כי לאחר המרת 0 ל -1, שיהיה לנו 0 כסכום, עלינו להיות שווים 0 ו- 1. לכן, בכל פעם שתמצא את ערך הסכום כ- 0, נגדיל את ערך הפלט. בהתחשב במערך הקלט, נעדכן את ערך הפלט בכל פעם שנקבל את הסכום כ- 0.

קופונים

קוד C ++ לספירת מערכי משנה עם מספר שווה של 1 ו- 0

#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

קוד Java לספירת מערכי משנה עם מספר שווה של 1 ו- 0

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 שמרנו את הסכום כמפתח, וכך מושגת מורכבות שטח לינארית.