資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用二進位制提升在 C++ 中查詢 N 個數字字首和中第一個大於或等於 X 的元素
在這個問題中，我們給定一個包含 N 個數字的陣列 arr[] 和一個整數值 x。我們的任務是建立一個程式，使用二進位制提升查詢 N 個數字的字首和中第一個大於或等於 X 的元素。
陣列元素的字首和是一個數組，其每個元素都是初始陣列中直到該索引的所有元素的總和。
例如 - array[] = {5, 2, 9, 4, 1}
prefixSumArray[] = {5, 7, 16, 20, 21}
讓我們舉個例子來理解這個問題，
Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3解決方案方法
在這裡，我們將使用二進位制提升的概念來解決問題。二進位制提升是將給定數字的值增加 2 的冪（透過翻轉位完成），範圍從 0 到 N。
我們將考慮類似於提升二叉樹的概念，我們將找到“P”索引的初始值。這透過翻轉位來增加，確保值不大於 X。現在，我們將考慮連同這個位置“P”一起提升。
為此，我們將開始翻轉數字的位，使得第 i 位翻轉不會使總和大於 X。現在，我們根據“P”的值有兩個情況 -
目標位置要麼位於“位置 + 2^i”和“位置 + 2^(i+1)”之間，其中第 i 次提升增加了值。或者，目標位置位於“位置”和“位置 + 2^i”之間。
使用此方法，我們將考慮索引位置。
示例
程式說明我們解決方案的工作原理
#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
prefSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
int P = 0;
int LOGN = log2(n);
if (x <= prefSum[0])
return 0;
for (int i = LOGN; i >= 0; i--) {
if (P + (1 << i) < n &&
prefSum[P + (1 << i)] < x) {
P += (1 << i);
}
}
return P + 1;
}
int main(){
int arr[] = { 5, 2, 9, 4, 1 };
int X = 19;
int n = sizeof(arr) / sizeof(arr[0]);
int prefSum[n] = { 0 };
generatePrefixSum(arr, prefSum, n);
cout<<"The index of first elements of the array greater than the given number is ";
cout<<findPreSumIndexBL(prefSum, n, X);
return 0;
}輸出
The index of first elements of the array greater than the given number is 3
更新於: 2022-02-01
217 次檢視
廣告