أول عدد صحيح سالب في كل نافذة بحجم k


مستوى الصعوبة متوسط
كثيرا ما يطلب في Accolite أمازون Paypal سوروكو
مجموعة طابور نافذة منزلقة

المشكلة بيان

توضح مشكلة "أول عدد صحيح سالب في كل نافذة بحجم 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) ، هنا كل منها يتوافق مع نافذة بحجم k.
  2. قم بتشغيل حلقة متداخلة لـ j يساوي i إلى (i + k) (غير مضمن). هذه الحلقة تعبر النافذة i.
  3. إذا كانت قيمة arr [j] سالبة ، اطبعها وانكسر ، وإلا استمر في البحث عن العنصر التالي.
  4. إذا لم يكن هناك عنصر سلبي في النافذة ، اطبع 0.

تحليل التعقيد

تعقيد الوقت = يا (ن * ك)
تعقيد الفضاء = يا (1)
حيث n هو عدد العناصر في المصفوفة المحددة.

نظرًا لأننا نحل المشكلة بشكل مستقل لكل نافذة بحجم k ، فإننا نتخطى عناصر n * k بشكل عام. وبالتالي التعقيد الزمني متعدد الحدود. وبما أننا لم نخزن أي شيء ، فإن تعقيد الفضاء ثابت.

كود جافا للعثور على أول عدد صحيح سالب في كل نافذة بحجم 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 وقم أيضًا بإضافة العنصر الجديد إلى Deque. إذا كانت Deque فارغة أثناء التحقق من العنصر السالب الأول ، فقم بطباعة 0.

  1. إنشاء صف مزدوج الذيل ف. ضع في اعتبارك النافذة الأولى بالحجم k.
  2. اجتياز عناصر الأول نافذة، إذا كان العنصر سالبًا ، فادفع مؤشره إلى نهاية Deque.
  3. في نهاية الاجتياز إذا كانت Deque فارغة طباعة 0 ، وإلا فإن العنصر الأول في Deque يتوافق مع فهرس العنصر السالب الأول.
  4. اجتياز المصفوفة المتبقية (ابدأ من الفهرس k إلى n - 1) ، بينما تكون مقدمة Deque أقل من (i - k) ، قم بإزالتها. إذا كان العنصر الحالي سالبًا ، فقم بإضافته إلى Deque.
  5. العنصر الأول في Deque يتوافق مع العنصر السلبي الأول لهذه النافذة ، إذا كان Deque فارغًا ، فلا يوجد عنصر سلبي في هذه النافذة ، اطبع 0.

تحليل التعقيد

تعقيد الوقت = O (ن)
تعقيد الفضاء = O (ن)
حيث n هو عدد العناصر في المصفوفة المحددة.

هنا ، لأننا استخدمنا قائمة انتظار ، يكون تعقيد الفضاء خطيًا. بالنسبة إلى تعقيد الوقت ، فقد اجتزنا ببساطة جميع عناصر المدخلات. وبالتالي ، فإن التعقيد الزمني خطي أيضًا.

كود جافا للعثور على أول عدد صحيح سالب في كل نافذة بحجم 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