K хэмжээтэй цонх бүрийн эхний сөрөг бүхэл тоо


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны PayPal Сороко
Array дараалал Гулгадаг цонх

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

“K хэмжээтэй цонх бүрийн эхний сөрөг бүхэл тоо” гэсэн асуудалд танд an гэсэн хариулт өгсөн болно массив эерэг ба сөрөг бүхэл тоонуудыг агуулсан тул 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) -тэй тэнцэх давталтыг ажиллуул.
  2. J-ийн үүрлэсэн гогцоог ажиллуул, i-ээс (i + k) -тай тэнцүү (оруулаагүй болно). Энэ давталт i цонхыг дайрч өнгөрдөг.
  3. Хэрэв arr [j] -н утга сөрөг байвал хэвлээд таславал дараагийн элементийг үргэлжлүүлэн шалгана уу.
  4. Хэрэв цонхонд сөрөг элемент байхгүй бол 0-ийг хэвлэ.

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

Цаг хугацааны нарийн төвөгтэй байдал = O (n * k)
Сансрын нарийн төвөгтэй байдал = O (1)
энд n нь өгөгдсөн массив дахь элементийн тоо юм.

K хэмжээтэй цонх бүрийн хувьд бид бие даан асуудлыг шийдэж байгаа тул ерөнхийдөө n * k элементээр дамжин өнгөрч байна. Тиймээс олон гишүүнт хугацааны нарийн төвөгтэй байдал. Бид юу ч хадгалаагүй тул орон зайн нарийн төвөгтэй байдал тогтмол байдаг.

K хэмжээтэй цонх бүрээс эхний сөрөг бүхэл тоог олох Java код

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

K + хэмжээтэй цонх бүрээс Эхний сөрөг бүхэл тоог олох C ++ код

#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. Бүтээх Дек q. K хэмжээтэй анхны цонхыг авч үзье.
  2. Эхний элементүүдийг хөндлөн гар цонх, хэрэв элемент сөрөг бол түүний индексийг Deque-ийн төгсгөл хүртэл түлхэх хэрэгтэй.
  3. Дэвлийн төгсгөлд Дек хоосон бол хэвлэх 0 бол Декийн эхний элемент нь эхний сөрөг элементийн индекстэй тохирч байна.
  4. Үлдсэн массивыг дайрч (k индексээс n - 1 хүртэл эхэлнэ), харин Deque-ийн урд хэсэг (i - k) -ээс бага байвал арилгана. Хэрэв одоогийн элемент сөрөг байвал Deque дээр нэмнэ үү.
  5. Deque-ийн эхний элемент нь энэ цонхны эхний сөрөг элементтэй тохирч байгаа бөгөөд Deque хоосон байвал энэ цонхонд сөрөг элемент байхгүй бол 0-ийг хэвлэ.

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

Цаг хугацааны нарийн төвөгтэй байдал = O (N)
Сансрын нарийн төвөгтэй байдал = O (N)
энд n нь өгөгдсөн массив дахь элементийн тоо юм.

Энд бид дараалал ашигласан тул орон зайн нарийн төвөгтэй байдал нь шугаман байна. Цаг хугацааны нарийн төвөгтэй байдлын хувьд бид оролтын бүх элементүүдийг дайран өнгөрсөн юм. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь мөн шугаман юм.

K хэмжээтэй цонх бүрээс Эхний сөрөг бүхэл тоог олох Java код

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

K + хэмжээтэй цонх бүрээс Эхний сөрөг бүхэл тоог олох C ++ код

#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