Re: [閒聊] 每日LeetCode已回收
724. Find Pivot Index
給定一個整數陣列 nums ，撰寫一函式回傳陣列的「樞紐」之索引值（從 0 開始數）。
我們定義樞紐為滿足陣列上的某位置之數字，其左邊的所有數字之和等於其右邊所有數字
之和。
如果樞紐不存在，我們應回傳 -1 。如果有多個樞紐，則回傳最左邊的樞紐之索引值。
限制：
nums 的長度位於 [0, 10000] 範圍之中。
nums[i] 之值位於 [-1000, 1000] 範圍之中。
Example 1:
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0
思路:
先算出nums的全部總和,後面區分num[0]與其他兩種情況,num[0]時,左邊總和為0,
故右邊總和為全部總和-num[0];
其他狀況時,左邊總和就是num[1]+...+num[i-1],迴圈從num[1]加上去,
右邊總和就是全部總和-左邊總和-num[i]
最後判斷左邊總和是否等於右邊總和,如相等,則樞紐=i並回傳樞紐值
如不相等,則繼續進行迴圈。
如若無樞紐,則回傳-1
C Code：
------------------
int pivotIndex(int* nums, int numsSize){
int pivotindex;
int leftsum=0;
int rightsum=0;
int totalsum=0;
for(int i=0; i<numsSize; i++){
totalsum += nums[i];
}
for(int i=0; i<numsSize; i++){
if(i == 0){
rightsum = totalsum - nums[i];
}else{
leftsum += nums[i-1];
rightsum = totalsum - leftsum - nums[i];
}
if(leftsum == rightsum){
pivotindex = i;
return pivotindex;
}
}
return -1;
}
------------------
補記:這題原本寫法會超時
後來修掉兩層迴圈才過關
今天學到時間複雜度的觀念 賺
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.119.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672063069.A.C14.html
推
12/26 22:01,
3年前
, 1F
12/26 22:01, 1F
→
12/26 22:04,
3年前
, 2F
12/26 22:04, 2F
推
12/26 22:06,
3年前
, 3F
12/26 22:06, 3F
※ 編輯: sustainer123 (223.137.14.32 臺灣), 12/26/2022 22:07:42
推
12/26 23:25,
3年前
, 4F
12/26 23:25, 4F
推
12/28 00:13,
2年前
, 5F
12/28 00:13, 5F
→
12/28 00:14,
2年前
, 6F
12/28 00:14, 6F
→
12/28 00:14,
2年前
, 7F
12/28 00:14, 7F
→
12/28 00:14,
2年前
, 8F
12/28 00:14, 8F
→
12/28 00:14,
2年前
, 9F
12/28 00:14, 9F
討論串 (同標題文章)
完整討論串 (本文為第 154 之 719 篇)：