Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหาองค์ประกอบที่ k ในซีรีส์ที่สร้างโดยช่วง N ที่กำหนดใน C++


ในปัญหานี้ เราได้รับช่วง N ของค่าจำนวนเต็มระหว่างช่วง L - R เป็นช่วงเมทริกซ์[N][2] และค่าจำนวนเต็ม k งานของเราคือ ค้นหาองค์ประกอบที่ k ในอนุกรมที่สร้างโดยช่วง N ที่กำหนด .

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input : ranges[][] = {{1, 3}, {5, 7}}, k = 4
Output : 5

คำอธิบาย

The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5.

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการสร้างชุดของจำนวนเต็มสำหรับช่วงที่กำหนด จากนั้นค้นหาองค์ประกอบที่ดัชนี k ของอาร์เรย์

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
   int rangeVal[10000];
   int rangeSize = 0;
   for(int i = 0; i < n; i++){
      for(int j = range[i][0]; j <= range[i][1]; j++){
         rangeVal[rangeSize] = j;
         rangeSize++;
      }
   }
   return rangeVal[k-1];
}
int main(){
   int L[] = { 1, 5 };
   int R[] = { 3, 8 };
   int range[][2] = {{1, 3}, {5, 8}};
   int n = sizeof(L) / sizeof(int);
   int k = 4;
   cout<<k<<"-th element of the series generated by ranges is "<<
   findKthSmallestEleSeries(n, k, range); 
   return 0;
}

ผลลัพธ์

4-th element of the series generated by ranges is 5

วิธีนี้เป็นวิธีที่ดีแต่อาจนำไปสู่ปัญหาหน่วยความจำได้หากช่วงมีขนาดใหญ่เกินไป ดังนั้นเราจึงต้องหาแนวทางที่ดีกว่าในการจัดเก็บองค์ประกอบทั้งหมดของอาร์เรย์

แนวทางอื่น

อีกวิธีในการแก้ปัญหาคือการใช้การค้นหาแบบไบนารีและอาร์เรย์ตัวนับ อาร์เรย์ตัวนับจะเก็บการนับจำนวนเต็มจนถึงช่วงที่กำหนด count[i] =จำนวนอักขระจนถึงช่วงที่ i

จากนั้นสำหรับ k เราจะหาช่วงหมายเลข i ซึ่งมีค่าน้อยที่สุดที่ k อยู่

แล้วเราจะหาค่าในช่วงนี้

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
   int start = 1;
   int end = n;
   int count[n + 1];
   count[0] = 0;
   for (int i = 0; i < n; i++)
      count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;
   int index = -1;
   int mid;
   while (start <= end) {
      mid = (start + end) / 2;
      if (count[mid] > k) {
         index = mid;
         end = mid - 1;
      }
      else if (count[mid] < k) 
         start = mid + 1;
      else {
         index = mid;
         break;
      }
   }
   start = range[index - 1][0];
   end = range[index - 1][1];
   int indexK = k - count[index - 1];
   while (start <= end) {
      mid = (start + end) / 2;
      if ((mid - range[index - 1][0]) + 1 == indexK) {
         return mid;
      }
      else if ((mid - range[index - 1][0]) + 1 > indexK)
         end = mid - 1;
      else
         start = mid + 1;
   }
   return -1;
}
int main(){
   int L[] = { 1, 5 };
   int R[] = { 3, 8 };
   int range[][2] = {{1, 3}, {5, 8}};
   int n = sizeof(L) / sizeof(int);
   int k = 4;
   cout<<k<<"-th element of the series generated by ranges is "<<
   findKthSmallestEleSeries(n, k, range);
   return 0;
}

ผลลัพธ์

4-th element of the series generated by ranges is 5