数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找数组中可能移动后左指针的索引
在这个问题中，我们给定一个大小为 N 的数组 arr[]。我们的任务是查找数组中可能移动后左指针的索引。
我们有两个数组指针，一个左指针和另一个右指针。
左指针从索引 0 开始，其值递增。
右指针从索引 (n-1) 开始，其值递减。
如果遍历的总和小于另一个，则指针的值增加，即如果左指针的总和小于右指针的总和，则左指针增加，否则右指针减少。并且总和更新。
让我们举个例子来理解这个问题，
Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2说明 -
leftPointer = 0 -> sum = 5, rightPointer = 5 -> sum = 4. Move rightPointer leftPointer = 0 -> sum = 5, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 1 -> sum = 11, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 2 -> sum = 14, rightPointer = 4 -> sum = 13. Move rightPointer leftPointer = 2 -> sum = 14, rightPointer = 3 -> sum = 20. Move rightPointer Position of the left pointer is 2.
解决方案方法
解决此问题的一个简单方法是根据总和移动 leftPointer 和 rightPointer。然后检查 leftPointer 是否比 rightPointer 大 1。
示例
程序说明我们解决方案的工作原理
#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
if(n == 1)
return 0;
int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
while (rightPointer > leftPointer + 1) {
if (leftPointerSum < rightPointerSum) {
leftPointer++;
leftPointerSum += arr[leftPointer];
}
else if (leftPointerSum > rightPointerSum) {
rightPointer--;
rightPointerSum += arr[rightPointer];
}
else {
break;
}
}
return leftPointer;
}
int main() {
int arr[] = { 5, 6, 3, 7, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
return 0;
}输出
The index of left pointer after moving is 2
更新于: 2022-01-28
111 次查看
广告