สมมติว่าเรามีรายการของจำนวนเต็มที่เรียงลำดับแล้ว k รายการ เราต้องค้นหาช่วงที่เล็กที่สุดที่มีอย่างน้อยหนึ่งหมายเลขจากแต่ละรายการ k ที่นี่ช่วง [a,b] มีขนาดเล็กกว่าช่วง [c,d] เมื่อ b-a
ดังนั้นหากอินพุตเป็น [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] ผลลัพธ์จะเป็น [14, 18]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- minRange :=inf, maxRange :=-inf, rangeSize :=inf, tempMinRange :=inf, tempMaxRange :=-inf
- n :=ขนาดของ nums
- กำหนดพอยน์เตอร์อาร์เรย์ที่มีขนาด n
- กำหนดลำดับความสำคัญของคิว pq
- สำหรับการเริ่มต้น i :=0 เมื่อฉัน
- แทรก { nums[i, 0], i } ลงใน pq
- tempMaxRange :=สูงสุดของ tempMaxRange และ nums[i, 0]
ในขณะที่ 1 ไม่ใช่ศูนย์ ให้ทำ − - กำหนดอุณหภูมิหนึ่งคู่ :=ด้านบนของ pq
- ลบองค์ประกอบออกจาก pq
- tempMinRange :=temp.first
- idx :=องค์ประกอบที่สองของอุณหภูมิ
- ถ้า tempMaxRange − tempMinRange
- rangeSize :=tempMaxRange - tempMinRange
- minRange :=tempMinRange
- maxRange :=tempMaxRange
(เพิ่มตัวชี้[idx] โดย 1)
ถ้าพอยน์เตอร์[idx] เท่ากับขนาดของ nums[idx] แล้ว −
มิฉะนั้น - tempMaxRange :=สูงสุดของ tempMaxRange และ nums[idx, pointers[idx]]
- แทรก { nums[idx, pointers[idx]], idx } ลงใน pq
กำหนดอาร์เรย์ขนาด 2
ans[0] :=minRange, ans[1] :=maxRange
คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include ใช้เนมสเปซ std;void print_vector(vector v){ cout <<"["; for(int i =0; i a, คู่ b){ return !(a.first smallestRange(vector>&nums) { int minRange =INT_MAX; int maxRange =INT_MIN; int rangeSize =INT_MAX; int tempMinRange, tempMaxRange, tempRangeSize; tempMinRange =INT_MAX; tempMaxRange =INT_MIN; int n =nums.size(); เวกเตอร์ พอยน์เตอร์(n); Priority_queue <คู่ , เวกเตอร์ <คู่ >, ตัวเปรียบเทียบ> pq; สำหรับ(int i =0; i temp =pq.top(); pq.pop(); tempMinRange =temp.first; int idx =temp.second; ถ้า (tempMaxRange - tempMinRange ans(2); ans[0] =minRange; ตอบ[1] =maxRange; กลับ ans; }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{4,10,15,25,26},{0,9,14,20},{5,18,24,30}}; print_vector(ob.smallestRange(v));}
อินพุต
<ก่อน>{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}}; ผลลัพธ์
[14, 18, ]
