网站 广州淘宝联盟建网站

网站 广州,淘宝联盟建网站,网页设计师证,做外贸一般做什么题目链接#xff1a;2529. 正整数和负整数的最大计数#xff08;简单#xff09; 算法原理#xff1a; 解法#xff1a;二分查找 模板#x1f447; 优选算法-二分#xff1a;18.在排序数组中查找元素的第一个和最后一个位置 利用题目的按 非递减顺序 排列的条件就可以二…题目链接2529. 正整数和负整数的最大计数简单算法原理解法二分查找模板优选算法-二分18.在排序数组中查找元素的第一个和最后一个位置利用题目的按 非递减顺序 排列的条件就可以二分处理了找到负数的最右端点和正数的最左端点思路一将二分查找的值设为定值间接找到不确定的值击败100.00%时间复杂度O(Logn)目标值定为0因为0恰好是二段性的节点因此可以有两种角度看待这个目标值0①左区间最右端的0[-5,-3-2-1,0,0,0,0,1,4,5,6]②右区间最左端的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)所以两次二分还是更稳妥些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); } }