C++で指定されたN個の範囲によって生成されたシリーズのk番目の要素を検索します

この問題では、行列範囲[N] [2]として間隔L〜Rの間にN範囲の整数値が与えられ、整数値kが与えられます。私たちのタスクは、指定されたN個の範囲によって生成されたシリーズのk番目の要素を見つけることです 。

問題を理解するために例を見てみましょう

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について、k番目に小さい値が存在する範囲番号iを見つけます。

次に、この範囲の値を見つけます。

例

ソリューションの動作を説明するプログラム

#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