מערך המשנה הארוך ביותר שיש ספירה של 1 שניות יותר מספירה של 0s


רמת קושי קַל
נשאל לעתים קרובות אקסנצ'ר אמזון בעברית דה שו סמסונג
מערך בליל

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

דוגמה

קלט:

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

פלט:

5

הסבר:

מאינדקס 0 עד 4, {1, 0, 1, 1, 0}, ישנם שלושה 1 ושני 0. רק ספירה אחת נוספת של 1 מאשר 0.

קלט:

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

פלט:

3

הסבר:

מאינדקס 0 עד 2, {1, 0, 1}, ישנם שני 1 ואחד 0. רק ספירה אחת נוספת של 1 מאשר 0.

אַלגוֹרִיתְם

  1. הכריזו על מפה.
  2. הגדר את הסכום ואת אורך התפוקה ל- 0.
  3. חצו את המערך, בעוד i = 0 עד i <n.
    1. בדוק אם arr [i] שווה ל- 0 אם נכון ואז הוסף -1 לסכום.
    2. אחרת הוסף +1 לסיכום.
    3. בדוק אם הסכום שווה ל- 1, ואז הגדל את ערך outputLength ב- 1.
    4. אחרת, בדוק אם מפה אינה מכילה את הסכום אם נכון ואז שים את הסכום והערך הנוכחי של i למפה יחד עם הסכום.
    5. בדוק אם מפה מכילה את (sum-1).
    6. אם outputLength קטן מ- i-index (ערך הסכום במפה).
      1. אם נכון, עדכן את outputLength ל- i-index.
  4. אורך פלט החזרה.

הסבר

נכריז א מַפָּה. במפה זו אנו הולכים לאחסן את ערך הסכום ואת הערך הנוכחי של אינדקס, אם התנאי מתקיים. קח שני משתנים והגדר את הסכום ל- 0 ואת outputLength ל- 0. בזמן חציית המערך, נבחר כל אלמנט של מערך ונבדוק אם arr [i] שווה ל- 0, אם נמצא שהוא שווה, נוסיף -1 לסכום ולאחסן אותו לסיכום, אחרת אם לא מצאנו שהוא 0, נוסיף את החיובי 1 לסכום ונאחסן אותו לסכום.

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

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

יישום

תוכנית C ++ למערך המשנה הארוך ביותר שיש ספירה של 1 שניות יותר מספירה של 0 שניות

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

תוכנית Java למערך המשנה הארוך ביותר שיש ספירה של 1 שניות יותר מספירה של 0 שניות

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

ניתוח מורכבות למערך המשנה הארוך ביותר שיש ספירה של 1 שניות יותר מספירה של 0 שניות

מורכבות זמן

O (n) איפה "N"  הוא מספר האלמנטים במערך.

מורכבות בחלל

O (n) איפה "N"  הוא מספר האלמנטים במערך.