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) —

推荐阅读:
梯形ABCD的面积是多少平方厘米  某校一年级同学平均身高是115厘米  若这稿件由乙完成,需要几小时?  从上边剪下一块直径是80厘米的圆片  甲乙丙三个修路队共同修完一条公路  最多可做多少面小三角旗  客车从甲地开往乙地需要10小时  遇店加一半,遇花喝一斗  这些车共有86个轮子  wordpress使用短代码实现在父页面中显示子页面列表链接 
评论列表
添加评论