サイズkのすべてのウィンドウの最初の負の整数


難易度 ミディアム
よく聞かれる アコライト Amazon (アマゾン) 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)に等しい場合にループを実行します。ここで、各iはサイズ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. トラバーサルの最後に、Dequeが空の場合は0を出力します。それ以外の場合、Dequeの最初の要素は最初の負の要素のインデックスに対応します。
  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