內蒙古做網站的公司購物網站
尋找數組的中心下標,鏈接奉上
方法
- 暴力循環(huán)
- 前綴和
暴力循環(huán)
???????思路:
依舊是我們的老朋友,暴力循環(huán)。
1.可以利用外層for循環(huán),循環(huán)變量為數組下標,在循環(huán)內分別求出下標左邊與右邊的sum
2.在邊界時討論,
當下標為左邊界(nums[0])時,left sum=0;當下標為右邊界(nums[numsSize-1)時,right sum=0
3.討論完特殊情況后,進行左邊與右邊的比較;
左==右時,即代表我們找到了下標;
否則返回-1。
代碼實現:
int pivotIndex(int* nums, int numsSize)
{for(int i=0;i<numsSize;i++)//外層for循環(huán){int Lsum=0;//left sum的縮寫。//在循環(huán)內部放置是因為防止這次的lsum加上上次的lsum,造成計算錯誤。if(i==0)//特殊情況,左邊界Lsum=0;elsefor(int j=0;j<i;j++)//求lsum的值Lsum+=nums[j];int Rsum=0;if(i==numsSize-1)Rsum=0;elsefor(int j=i+1;j<numsSize;j++)Rsum+=nums[j];if(Lsum==Rsum)return i;}return -1;
}
但是,此種方法的時間復雜度巨大無比,我們可以進行改進
我們發(fā)現,每次進入for循環(huán)內時,總是會有重復的計算出現,比如:
計算i=0時的Rsum(ringt sum縮寫),每次都重新計算了一遍,但是我們可以在上一次的基礎上進行減nums[i],大大降低了計算量。
代碼實現:
int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=0;i<numsSize;i++)//首先計算出Rsum的值,i=0時{Rsum+=nums[i];}for(i=0;i<numsSize;i++){if(i==0)Lsum=0;elseLsum+=nums[i-1];//上一次的基礎上加上nums[i-1]if(i==numsSize-1)Rsum=0;elseRsum-=nums[i];//上一次的基礎上減上nums[i]if(Lsum==Rsum)return i;}return -1;
}
但是這樣每次進循環(huán)都會判斷一次是否在邊界處
則可以在外部進行判斷
int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=1;i<numsSize;i++)Rsum+=nums[i];if(Lsum==Rsum)return 0;for(i=1;i<numsSize;i++){Lsum+=nums[i-1];Rsum-=nums[i];if(Lsum==Rsum)return i;}return -1;
}
前綴和
思路:
當找到下標時,意味著左右元素和相等。
設數組和為total,則total==Rsum+Lsum+nums[i]
又因左右相等,故total==2Rsum+nums[i]
代碼實現:
int pivotIndex(int* nums, int numsSize)
{int total=0;int Rsum=0;for(int i=0;i<numsSize;i++){total+=nums[i];}for(int i=0;i<numsSize;i++){if(Rsum*2+nums[i]==total)return i;Rsum+=nums[i];}return -1;
}
歡迎討論哦