在 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。

示例

程序说明我们解决方案的工作原理

Open Compiler
#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; }

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

The index of left pointer after moving is 2

更新于: 2022-01-28

111 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告