크기가 k 인 모든 창에서 첫 번째 음의 정수

난이도 중급
자주 묻는 질문 수행자 아마존 페이팔 소로코
배열 슬라이딩 윈도우조회수 48

문제 정책

“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. 만들기 데케 큐. 크기 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
Translate »