차례
문제 정책
“k 크기의 모든 창에서 첫 번째 음의 정수”문제는 정렬 양의 정수와 음의 정수를 포함하고, 크기 k의 모든 창에 대해 해당 창에서 첫 번째 음의 정수를 인쇄합니다. 창에 음의 정수가 없으면 0 (영)을 출력합니다.
예
arr[] = {5, -2, 3, 4, -5}
k = 2
-2 -2 0 -5
arr[] = {7, 9, -1, 2, 3, 4, -2, -3, -4}
k = 3
-1 -1 -1 0 -2 -2 -2
순진한 접근
크기가 k 인 모든 창에 대해 창의 모든 요소를 가로 질러 첫 번째 음의 정수를 인쇄합니다.
- i가 0에서 (n – k) 인 경우 루프를 실행합니다. 여기서 각 i는 크기가 k 인 창에 해당합니다.
- j가 i ~ (i + k) (포함되지 않음)에 대해 중첩 루프를 실행합니다. 이 루프는 창 i를 가로지 릅니다.
- arr [j]의 값이 음수이면 인쇄하고 중단하고, 그렇지 않으면 계속해서 다음 요소를 확인합니다.
- 창에 음수 요소가 없으면 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을 인쇄합니다.
- 만들기 데케 큐. 크기 k의 첫 번째 창을 고려하십시오.
- 첫 번째 요소를 횡단 창, 요소가 음수이면 해당 인덱스를 Deque 끝으로 푸시합니다.
- 순회가 끝날 때 Deque가 비어 있으면 0을 인쇄하고, 그렇지 않으면 Deque의 첫 번째 요소가 첫 번째 음수 요소의 인덱스에 해당합니다.
- 나머지 배열 (인덱스 k에서 n – 1까지)을 트래버스하고 Deque의 앞쪽은 (i – k)보다 작습니다. 현재 요소가 음수이면 Deque에 추가합니다.
- 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
