How to Find Pivot Index of Array?
- 时间:2020-10-11 15:48:46
- 分类:网络文摘
- 阅读:92 次
Given an array of integers nums, write a method that returns the “pivot” index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
Example 1:
Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.Example 2:
Input:
nums = [1, 2, 3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.Note:
The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].
C++ Finding Pivot Index of Array Algorithm
We can compute the accumulated sums from both ends and store them in two arrays namely e.g. sum_left and sum_right. Both steps take O(N) in time and complexity. Then we need another O(N) step to go through N indices and find out if there is a index such that sum_left[i] = sum_right[i].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: int pivotIndex(vector<int>& nums) { vector<int> sum_left = nums, sum_right = nums; for (int i = 1; i < sum_left.size(); ++ i) { sum_left[i] += sum_left[i - 1]; } for (int i = sum_right.size() - 2; i >= 0; -- i) { sum_right[i] += sum_right[i + 1]; } for (int i = 0; i < nums.size(); ++ i) { if (sum_left[i] == sum_right[i]) { return i; } } return -1; } }; |
class Solution { public: int pivotIndex(vector<int>& nums) { vector<int> sum_left = nums, sum_right = nums; for (int i = 1; i < sum_left.size(); ++ i) { sum_left[i] += sum_left[i - 1]; } for (int i = sum_right.size() - 2; i >= 0; -- i) { sum_right[i] += sum_right[i + 1]; } for (int i = 0; i < nums.size(); ++ i) { if (sum_left[i] == sum_right[i]) { return i; } } return -1; } };
The above implementation is straightforward, at the cost of two O(N) additional space which can be avoided if we go with the following approach: first we need O(N) time to compute the sum. Then, we need to store the current partial sum (prefix-sum) from the begining of the array. Then we can compute the sum from the end by using the math equation (sum – prefix_sum – current element).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: int pivotIndex(vector<int>& nums) { int sum = 0; for (const auto &n: nums) sum += n; int psum = 0; for (int i = 0; i < nums.size(); ++ i) { if (sum - psum - nums[i] == psum) { return i; } psum += nums[i]; } return -1; } }; |
class Solution { public: int pivotIndex(vector<int>& nums) { int sum = 0; for (const auto &n: nums) sum += n; int psum = 0; for (int i = 0; i < nums.size(); ++ i) { if (sum - psum - nums[i] == psum) { return i; } psum += nums[i]; } return -1; } };
O(N) time complexity and O(1) space complexity.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:委托建站公司搭建的网站,会涉嫌源码侵权? 99%的网站死于太丑!!! 黑帽SEO圈里流行"反推技术秒收" 企业网站建设如何选择企业建站系统? 游桃花园作文400字 留意幸福角 钉扣子作文400字 清明随感作文 论威严的重要性 拥有一颗周全的心作文
- 评论列表
-
- 添加评论