leetcode 724 Find Pivot Index

starsfun 發布于2019-08-15 14:01 / 2185人閱讀

摘要：左邊的元素和為，剛好等于右邊的元素和。在第二趟遍歷中，檢查當前元素左邊所有元素的加和，是否等于減去當前元素的值，如果滿足，則當前點為樞紐點，返回當前元素的位置。

題目詳情

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. 題目的意思要找出輸入數組的“樞紐”點。這個“樞紐”的定義就是，這個元素所有左邊的元素的加和剛好等于它所有右邊元素的加和，并且我們返回這個樞紐點的位置。如果不存在這樣的“樞紐”，則返回－1.如果有多個這樣的樞紐，則返回最左側的樞紐點。
Example 1:
Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
nums[3]左邊的元素和為11，剛好等于nums[3]右邊的元素和。
Example 2:
Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
沒有滿足“樞紐”定義的元素。所以返回－1.

想法

有一種臨界情況需要考慮，就是元素nums[0]作為樞紐點的情況，這種情況下，nums[0]的所有的右邊的元素加和應該為0，則nums[0]為數組的樞紐點。

考慮了這個特殊情況就沒有什么特別的了。我們先遍歷一趟獲得數組元素值的和sum。

在第二趟遍歷中，檢查當前元素左邊所有元素的加和，是否等于sum減去當前元素的值，如果滿足，則當前點為樞紐點，返回當前元素的位置。

解法

    public int pivotIndex(int[] nums) {
        int length = nums.length;
        if(length == 0 || length ==1)return -1;
        int sum = 0;
        
        for(int num : nums)sum += num;
        
        if(sum-nums[0] == 0)return 0;
        int left = 0;
        for(int i=1;i

GPU云服務器云服務器 Pivot 724服務器云監控平臺 Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68457.html

[LeetCode] 724. Find Pivot Index

Problem 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 equa...

vibiu 2019-08-16 13:49 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
Wiggle Sort & II

摘要：如果沒復雜度的要求，先也可以，再交叉放入數字也可以。交叉的時候注意是按照，降序的。 Wiggle Sort 題目鏈接：https://leetcode.com/problems... 這道題允許等號，相對簡單，有兩種方法：1. sort然后交換奇數位和它下一位的元素，2. 不滿足條件的時候直接交換可以用遞推來說明一下這么做的正確性：假設到第i位之前都滿足題目要求的關系現在比較...

Moxmi 2019-08-14 17:18 評論0 收藏0
9 .leetcode Peak Index in a Mountain Array

摘要：題目例子我的解法其他解法求最大值然后求二分法查找 1 題目 Lets call an array A a mountain if the following properties hold: A.length >= 3There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[...

txgcwm 2019-08-23 16:56 評論0 收藏0