福州軟件優(yōu)化網站建設,做紡織都有那些好網站,山西公司注冊網上核名,品牌營銷方案模板題目鏈接#xff1a;2529. 正整數和負整數的最大計數#xff08;簡單#xff09; 算法原理#xff1a; 解法#xff1a;二分查找 模板#x1f447; 優(yōu)選算法-二分#xff1a;18.在排序數組中查找元素的第一個和最后一個位置 利用題目的按 非遞減順序 排列的條件就可以二…題目鏈接2529. 正整數和負整數的最大計數簡單算法原理解法二分查找模板優(yōu)選算法-二分18.在排序數組中查找元素的第一個和最后一個位置利用題目的按 非遞減順序 排列的條件就可以二分處理了找到負數的最右端點和正數的最左端點思路一將二分查找的值設為定值間接找到不確定的值擊敗100.00%時間復雜度O(Logn)目標值定為0因為0恰好是二段性的節(jié)點因此可以有兩種角度看待這個目標值0①左區(qū)間最右端的0[-5,-3-2-1,0,0,0,0,1,4,5,6]②右區(qū)間最左端的0[-5,-3-2-1,0,0,0,0,1,4,5,6]第一次遍歷找到 最左端的0 進而找到 最后一個負數 二分查找結束后left和right在0沒有0就在0的右側先處理邊界情況看是否全是負數是0或者正數就正常更新長度即可第二次遍歷找到 最右端的0 進而找到 第一個正數 二分查找結束后left和right在0沒有0就在0的左側先處理邊界情況看是否全是正數是0或者負數就正常更新長度即可思路二直接將二分查找的值設為要找的不確定值擊敗100.00%時間復雜度O(Logn)比思路一好寫一些但是要理解好每一步這里的if判斷是帶等號的因為0不算正數也不算負數等于0的時候也要相應移動答疑Q1能不能用一次二分就找到最后的負數和第一個正數呢能的比如先找到最后一個負數的位置然后left右移找到第一個正數的位置但是不保證時間復雜度一定是logn因為當數據[-1,0,0,0,0,0,~,0,0,0,2]的時候left一直右移就會將時間復雜度弱化到O(N)所以兩次二分還是更穩(wěn)妥些Java代碼class Solution { public int maximumCount(int[] nums) { //利用題目的按 非遞減順序 排列的條件就可以二分處理了 //找到負數的最右端點和正數的最左端點 int nnums.length; if(n0) return 0; //利用0來決定二段性負數 0 正數 //先找最后一個負數(通過最左側的0來找) int left0,rightn-1; while(leftright){ int midleft(right-left)/2; if(nums[mid]0) leftmid1; else rightmid; } //此時在0或者0的右側正數 int neg0; //全是負數 if(nums[left]0) negn; //是0或者正數 else negleft; //再找第一個正數(通過最右側的0來找) left0;rightn-1; while(leftright){ int midleft(right-left1)/2; if(nums[mid]0) rightmid-1; else leftmid; } //此時在0或者0的左側 int pos0; //全是正數 if(nums[left]0) posn; //是0或者負數 else posn-(left1); return Math.max(neg,pos); } }class Solution { //思路二直接將二分查找的值設為要找的不確定值 public int maximumCount(int[] nums) { int nnums.length; if(n0) return 0; int left0,rightn-1; //找到負數的最后一個位置 while(leftright){ int midleft(right-left1)/2; if(nums[mid]0) rightmid-1; else leftmid; } int negnums[left]0?left1:0; //找到正數的第一個位置 left0;rightn-1; while(leftright){ int midleft(right-left)/2; if(nums[mid]0) leftmid1; else rightmid; } int posnums[left]0?n-left:0; return Math.max(neg,pos); } }