資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告