ค้นหาช่วงที่เล็กที่สุดที่มีองค์ประกอบจากรายการ k ใน C++

สมมติว่าเรามี 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 เมื่อ i

  • แทรก { nums[i, 0], i } ลงใน pq

  • tempMaxRange :=สูงสุดของ tempMaxRange และ nums[i, 0]

• ในขณะที่ 1 ไม่ใช่ศูนย์ ให้ทำ -

  • กำหนดหนึ่งคู่ temp :=ด้านบนของ 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));}

อินพุต

ผลลัพธ์

[14, 18, ]