המספר השלילי השלילי הראשון בכל חלון בגודל k


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית פייפאל סורוקו
מערך תור חלון הזזה

הצהרת בעיה

הבעיה "מספר שלם שלילי ראשון בכל חלון בגודל k" קובעת שקיבלתם מערך המכיל מספרים שלמים חיוביים ושליליים, עבור כל חלון בגודל k הדפיסו את המספר השלילי השלילי הראשון בחלון זה. אם אין מספר שלם שלילי בשום חלון אז פלט 0 (אפס).

דוגמאות

arr[] = {5, -2, 3, 4, -5}
k = 2
-2 -2 0 -5

 

המספר השלילי השלילי הראשון בכל חלון בגודל k

arr[] = {7, 9, -1, 2, 3, 4, -2, -3, -4}
k = 3
-1 -1 -1 0 -2 -2 -2

גישה נאיבית

בכל חלון בגודל k, חצו את כל רכיבי החלון והדפיסו את המספר השלילי השלילי הראשון.

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

ניתוח מורכבות

מורכבות זמן = O (n * k)
מורכבות בחלל = O (1)
כאשר n הוא מספר האלמנטים במערך הנתון.

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

קוד Java כדי למצוא את המספר השלם השלילי הראשון הראשון בכל חלון בגודל k

class FirstNegativeIntegerInEveryWindowOfSizeK {
    private static void firstNegativeInteger(int[] arr, int k) {
        int n = arr.length;

        // Run a loop corresponding to every window in the array
        for (int i = 0; i <= n - k; i++) {
            boolean negFound = false;
            // Traverse the window
            for (int j = i; j < i + k; j++) {
                // If current element if negative print it
                if (arr[j] < 0) {
                    System.out.print(arr[j] + " ");
                    negFound = true;
                    break;
                }
            }

            // if there is no negative element then print 0
            if (!negFound)
                System.out.print("0 ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, -2, 3, 4, -5};
        int k1 = 2;
        firstNegativeInteger(arr1, k1);

        // Example 2
        int arr2[] = new int[]{7, 9, -1, 2, 3, 4, -2, -3, -4};
        int k2 = 3;
        firstNegativeInteger(arr2, k2);
    }
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

קוד C ++ לאיתור מספר שלם שלילי ראשון בכל חלון בגודל k

#include<bits/stdc++.h> 
using namespace std; 

void firstNegativeInteger(int *arr, int k, int n) {
    // Run a loop corresponding to every window in the array
    for (int i = 0; i <= n - k; i++) {
        bool negFound = false;
        // Traverse the window
        for (int j = i; j < i + k; j++) {
            // If current element if negative print it
            if (arr[j] < 0) {
                cout<<arr[j]<<" ";
                negFound = true;
                break;
            }
        }
        
        // if there is no negative element then print 0
        if (!negFound)
            cout<<"0 ";
    }
    
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {5, -2, 3, 4, -5};
    int k1 = 2;
    firstNegativeInteger(arr1, k1, sizeof(arr1) / sizeof(arr1[0]));

    // Example 2
    int arr2[] = {7, 9, -1, 2, 3, 4, -2, -3, -4};
    int k2 = 3;
    firstNegativeInteger(arr2, k2, sizeof(arr2) / sizeof(arr2[0]));
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

גישה אופטימלית

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

  1. צור deque ש. שקול את החלון הראשון בגודל k.
  2. חצו את האלמנטים של הראשון חלון, אם האלמנט שלילי, דחף את האינדקס שלו לסוף הדק.
  3. בסוף המעבר אם הדק ריק ריק, הדפס 0, אחרת האלמנט הראשון בדק תואם את אינדקס האלמנט השלילי הראשון.
  4. חצה במערך הנותר (התחל מאינדקס k עד n - 1), ואילו החלק הקדמי של Deque קטן מ- (i - k) הסר אותו. אם האלמנט הנוכחי שלילי, הוסף אותו ל- Deque.
  5. האלמנט הראשון ב- Deque תואם את האלמנט השלילי הראשון עבור חלון זה, אם ה- Deque ריק, אין אלמנט שלילי בחלון זה, הדפס 0.

ניתוח מורכבות

מורכבות זמן = O (n)
מורכבות בחלל = O (n)
כאשר n הוא מספר האלמנטים במערך הנתון.

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

קוד Java כדי למצוא מספר שלם שלילי ראשון בכל חלון בגודל k

import java.util.Deque;
import java.util.LinkedList;

class FirstNegativeIntegerInEveryWindowOfSizeK {
    private static void firstNegativeInteger(int[] arr, int k) {
        int n = arr.length;

        // create a deque q
        Deque<Integer> q = new LinkedList<>();
        // traverse the first window
        for (int i = 0; i < k; i++) {
            // if the current element is negative add it to the end of deque
            if (arr[i] < 0)
                q.addLast(i);
        }

        // if deque is not empty, front of deque is the index of first negative element
        // else there is no negative element in this window
        if (!q.isEmpty())
            System.out.print(arr[q.peek()] + " ");
        else
            System.out.print("0 ");

        for (int i = k; i < n; i++) {
            // remove previous window elements
            while (!q.isEmpty() && q.peek() <= (i - k)) {
                q.removeFirst();
            }

            // if the current element is negative, add it to the deque
            if (arr[i] < 0)
                q.addLast(i);

            // if deque is not empty, front of deque is the index of first negative element
            // else there is no negative element in this window
            if (!q.isEmpty())
                System.out.print(arr[q.peek()] + " ");
            else
                System.out.print("0 ");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, -2, 3, 4, -5};
        int k1 = 2;
        firstNegativeInteger(arr1, k1);

        // Example 2
        int arr2[] = new int[]{7, 9, -1, 2, 3, 4, -2, -3, -4};
        int k2 = 3;
        firstNegativeInteger(arr2, k2);
    }
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2

קוד C ++ לאיתור מספר שלם שלילי ראשון בכל חלון בגודל k

#include<bits/stdc++.h> 
using namespace std; 

void firstNegativeInteger(int *arr, int k, int n) {
    // create a deque q
    deque<int> q;
    
    // traverse the first window
    for (int i = 0; i < k; i++) {
        // if the current element is negative add it to the end of deque
        if (arr[i] < 0)
            q.push_back(i);
    }
    
    // if deque is not empty, front of deque is the index of first negative element
    // else there is no negative element in this window
    if (!q.empty())
        cout<<arr[q.front()]<<" ";
    else
        cout<<"0 ";
        
    for (int i = k; i < n; i++) {
        // remove previous window elements
        while (!q.empty() && q.front() <= (i - k)) {
            q.pop_front();
        }
        
        // if the current element is negative, add it to the deque
        if (arr[i] < 0)
            q.push_back(i);
            
        // if deque is not empty, front of deque is the index of first negative element
        // else there is no negative element in this window
        if (!q.empty())
            cout<<arr[q.front()]<<" ";
        else 
            cout<<"0 ";
    }
    
    cout<<endl;
}

int main() {
    // Example 1
    int arr1[] = {5, -2, 3, 4, -5};
    int k1 = 2;
    firstNegativeInteger(arr1, k1, sizeof(arr1) / sizeof(arr1[0]));

    // Example 2
    int arr2[] = {7, 9, -1, 2, 3, 4, -2, -3, -4};
    int k2 = 3;
    firstNegativeInteger(arr2, k2, sizeof(arr2) / sizeof(arr2[0]));
}
-2 -2 0 -5 
-1 -1 -1 0 -2 -2 -2