每個大小為k的窗口中的第一個負整數


難度級別
經常問 ol石 亞馬遜 貝寶 索羅科
排列 隊列 滑動窗口

問題陳述

問題“在大小為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和滑動窗口技術。 雙端隊列將負數元素的索引存儲在窗口中。 雙端隊列的第一個元素對應於窗口中第一個負元素的索引。 更改窗口時,從雙端隊列中刪除先前的窗口元素,並將新元素添加到雙端隊列中。 如果在檢查第一個負數元素時雙端隊列為空,則打印0。

  1. 創建一個 雙端隊列 q。 考慮大小為k的第一個窗口。
  2. 遍歷第一個元素 窗口,如果元素為負,則將其索引推到Deque的末尾。
  3. 在遍歷結束時,如果雙端隊列為空,則打印0,否則雙端隊列中的第一個元素對應於第一個負元素的索引。
  4. 遍歷其餘數組(從索引k到n – 1),而Deque的前部小於(i – k)刪除它。 如果當前元素為負,則將其添加到Deque。
  5. 雙端隊列中的第一個元素對應於此窗口的第一個負元素,如果雙端隊列為空,則此窗口中沒有負元素,則打印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