数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找由给定 N 个范围生成的序列中的第 k 个元素
在这个问题中，我们给定了一个 N 个整数范围，这些范围在区间 L - R 之间，作为一个矩阵 range[N][2] 和一个整数 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，我们将找到第 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
更新于: 2022年1月28日
200 次查看
广告