数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告