秦皇岛做网站优化,青岛网站建设eoe,西安市房产信息查询平台官网,一个人做网站要多久leetcode LCP 28. 采购方案 小力将 N 个零件的报价存于数组 nums。小力预算为 target#xff0c;假定小力仅购买两个零件#xff0c;要求购买零件的花费不超过预算#xff0c;请问他有多少种采购方案。 注意#xff1a;答案需要以 1e9 7 (1000000007) 为底取模#xff0c…leetcode LCP 28. 采购方案 小力将 N 个零件的报价存于数组 nums。小力预算为 target假定小力仅购买两个零件要求购买零件的花费不超过预算请问他有多少种采购方案。 注意答案需要以 1e9 7 (1000000007) 为底取模如计算初始结果为1000000008请返回 1 示例 1 输入nums [2,5,3,5], target 6 输出 解释预算内仅能购买 nums[0] 与 nums[2]。 示例 2 输入nums [2,2,1,9], target 10 输出4 解释符合预算的采购方案如下 nums[0] nums[1] 4 nums[0] nums[2] 3 nums[1] nums[2] 3 nums[2] nums[3] 10 提示 2 nums.length 10^5 1 nums[i], target 10^5 看着简单找出数组中两个元素之和小于等于给定值的组合个数。是不是挺简单的但事实却并不简单问题在于运行时间。
1. 首先使用蛮力法 代码
int purchasePlans(int* nums, int numsSize, int target){int count 0;for (int i 0; i numsSize; i) {for (int j i 1; j numsSize; j) {if (nums[i] nums[j] target) count;}count count % 1000000007;}return count;
}从第一个元素开始向后遍历判断两元素之后是否小于 target小于则计数加一。时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 这里从第 0 个元素开始向后遍历还是从第 1 个元素开始向前遍历是一样的时间复杂度都是 O ( n 2 ) O(n^2) O(n2) 。 使用上述方法在数组元素过长时就会超时。
2. 排序 “蛮力”
void quikSort(int * nums, int start, int end) {if (start end) {int left start, right end;int target nums[start];while (left right) {while (left right nums[right] target) right--;if (left right) {nums[left] nums[right];left;}while (left right nums[left] target) left;if (left right) {nums[right] nums[left];right--;}}nums[right] target;quikSort(nums, start, right - 1);quikSort(nums, right 1, end);}
}int purchasePlans(int* nums, int numsSize, int target){quikSort(nums, 0, numsSize - 1);if (nums[1] nums[0] target) {return 0;}int count 1;int pre 1;for (int i 2; i numsSize; i) {if (nums[i] nums[i - 1] target) {pre i - 1;} else {while (pre 0) {if (nums[i] nums[pre] target) break;pre--;}}if (pre -1) break;count (pre 1);count % 1000000007;}return count;
}先对数组进行排序这里使用快速排序其时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn), 但是当数组原本有序的情况下其时间复杂度会变为 O ( n 2 ) O(n^2) O(n2)这也是这种方法也不可行的原因。
在排序后判断统计阶段
判断第 0 个和第 1 个 元素是否满足 nums[0] nums[1] target
满足初始化 pre上一个元素满足的最大下标 为 1count 也为 1不满足直接返回 0 连最小的两个元素都无法满足后面的一定也无法满足
判断当前元素与前一个元素是否满足 nums[i] nums[i - 1] target:
满足修改 pre 的值 i - 1 在这种情况下当前值还不够大相邻元素是符合要求的。 不满足从 pre 开始寻找满足条件的的元素的下标。 上一个元素不能满足当前元素一定不能满足因为其为一个递增序列。
count (pre 1) 下标为 pre 的元素能满足则其前面的元素一定也能满足。 这里还有一步如果这个 pre 已经为 -1 即当前值已经大于 target则直接退出循环后面的值都大于 target。无需再进行计算了。 这一阶段其时间复杂度为 O ( n ) O(n) O(n)可能会出现元素值跨度很大的情况即在寻找符合条件的 pre 时循环了较长时间但是对整体影响不大。
此方法时间消耗主要在排序阶段当原始已经有序的情况下再使用快速排序其时间消耗也是较大的。
