Leetcode—2529.正整数和负整数的最大计数【简单】

2023每日刷题（四）

Leetcode—2529.正整数和负整数的最大计数

遍历法实现代码

int maximumCount(int* nums, int numsSize){int i;int neg = 0, pos = 0;for(i = 0; i < numsSize; i++) {if(nums[i] < 0) {neg++;}if(nums[i] > 0) {pos++;}}return (neg > pos) ? neg : pos;
}

测试结果

二分法思想

本质是循环不变量

图片源于灵茶山艾府

实现代码

int lower_bound(int *nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;   // 闭区间[left, right]int mid;while(left <= right) {      //区间不为空mid = left + (right - left) / 2;if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;
}int lower_bound2(int *nums, int numsSize, int target) {int left = 0;int right = numsSize;   // 左闭右开区间[left, right)int mid;while(left < right) {      //区间不为空mid = left + (right - left) / 2;if(nums[mid] < target) {left = mid + 1;     // [mid + 1, right)} else {right = mid;    // [left, mid)}}return left;     //return right也可以，因为right和left都指向同一个数了
}int lower_bound3(int *nums, int numsSize, int target) {int left = -1;int right = numsSize;   // 开区间(left, right)int mid;while(left+1 < right) {      //区间不为空mid = left + (right - left) / 2;if(nums[mid] < target) {left = mid;     // (mid, right)} else {right = mid;    // (left, mid)}}return right;      
}int maximumCount(int* nums, int numsSize){int i;int neg = 0, pos = 0;// int tmp = lower_bound(nums, numsSize, 0);// int tmp = lower_bound2(nums, numsSize, 0);int tmp = lower_bound3(nums, numsSize, 0);neg = tmp;// tmp = lower_bound(nums, numsSize, 1);// tmp = lower_bound2(nums, numsSize, 1);tmp = lower_bound3(nums, numsSize, 1);if(tmp == numsSize) {pos = 0;} else {pos = numsSize - tmp;}return (neg > pos) ? neg : pos;
}

使用lower_bound()、lower_bound2()还是lower_bound3()都能成功，这里只是提供三种二分查找函数，我更偏向于第二种

测试结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！