ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยค่าจำนวนเต็ม N ค่า และหน้าต่างขนาด N ภารกิจของเราคือ สร้างโปรแกรมหาจำนวนเต็มลบแรกในทุกหน้าต่างขนาด k เราจะพิมพ์จำนวนลบแรกหากมีอยู่ มิฉะนั้นพิมพ์ 0 หมายถึงไม่มีจำนวนลบ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2 Output: -2, -1, -1, 0, -6
คำอธิบาย -
ขนาดหน้าต่าง k = 2, {-2, 2}, จำนวนลบแรกคือ -2 {2, -1}, จำนวนลบแรกคือ -1 {-1, 4}, จำนวนลบแรกคือ -1 {4, 3}, จำนวนลบแรกคือ 0 (ไม่มีจำนวนลบ) {3, -6}, จำนวนลบแรกคือ -6
วิธีการแก้ปัญหา
วิธีง่ายในการแก้ปัญหาคือการเดินทางผ่านอาร์เรย์ arr[] สร้างหน้าต่างขนาด k และในแต่ละหน้าต่างหาจำนวนเต็มลบแรกและพิมพ์
วิธีนี้เป็นวิธี naive ที่ใช้ลูปซ้อนสองชั้นสำหรับการดำเนินการ ดังนั้นความซับซ้อนของเวลาคือ O(n*k)
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <iostream> using namespace std; void findFirstNegIntWindowK(int arr[], int n, int k){ bool negFound; for (int i = 0; i<(n-k+1); i++) { negFound = false; for (int j = 0; j<k; j++) { if (arr[i+j] < 0) { cout<<arr[i+j]<<"\t"; negFound = true; break; } } if (!negFound) cout<<"0\t"; } } int main(){ int arr[] = {-2, 2, -1, 4, 3, -6}; int n = sizeof(arr)/sizeof(arr[0]); int k = 2; cout<<"First negative integer in each with of size "<<k<<" is \n"; findFirstNegIntWindowK(arr, n, k); return 0; }
เอาต์พุต
First negative integer in each with of size 2 is -2 -1 -1 0 -6
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้แนวคิดคล้าย sliding window สำหรับนี้ เราจะสร้าง dequeue (คิวสองปลาย) ขนาด k สำหรับองค์ประกอบทั้งหมดของหน้าต่างขนาด k เราจะเริ่มเดินทางผ่านอาร์เรย์จากต้นทางและเติมองค์ประกอบใน dequeue ขนาด k และจากนั้น สำหรับแต่ละองค์ประกอบของอาร์เรย์ เราจะลบองค์ประกอบหนึ่งจากปลายหนึ่งและเพิ่มองค์ประกอบหนึ่งอีกปลาย สำหรับหน้าต่างที่เลื่อนแต่ละครั้ง เราจะหาและพิมพ์จำนวนลบแรก สำหรับการหาจำนวนลบ เราจะตรวจสอบว่าจำนวนที่ถูกลบออกเป็นจำนวนลบแรกของหน้าต่างหรือไม่ ถ้าใช่ เราจะตรวจสอบองค์ประกอบถัดไปสำหรับจำนวนลบแรก มิฉะนั้นไม่
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <bits/stdc++.h> using namespace std; void findFirstNegIntWindowK(int arr[], int n, int k){ deque<int> windowKsize; int i = 0; for (; i < k; i++) if (arr[i] < 0) windowKsize.push_back(i); for (; i < n; i++){ if (!windowKsize.empty()) cout<<arr[windowKsize.front()]<<"\t"; else cout<<"0\t"; while ( (!windowKsize.empty()) && windowKsize.front() < (i - k + 1)) windowKsize.pop_front(); if (arr[i] < 0) windowKsize.push_back(i); } if (!windowKsize.empty()) cout<<arr[windowKsize.front()]<<" \t"; else cout<<"0\t"; } int main(){ int arr[] = {-2, 2, -1, 4, 3, -6}; int n = sizeof(arr)/sizeof(arr[0]); int k = 2; cout<<"First negative integer in each with of size "<<k<<" is \n"; findFirstNegIntWindowK(arr, n, k); return 0; }
เอาต์พุต
First negative integer in each with of size 2 is -2 -1 -1 0 -6
