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

news/2025/2/5 14:54:35/

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; 	// 也可以是right + 1
}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;      // 也可以是left + 1
}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;
}