力扣LCP18.早餐组合

题目

小扣在秋日市集选择了一家早餐摊位&＃xff0c;一维整型数组 staple 中记录了每种主食的价格&＃xff0c;一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料&＃xff0c;且花费不超过 x 元。请返回小扣共有多少种购买方案。

注意&＃xff1a;答案需要以 1e9 &＃43; 7 (1000000007) 为底取模&＃xff0c;如&＃xff1a;计算初始结果为&＃xff1a;1000000008&＃xff0c;请返回 1
示例 1&＃xff1a;

输入&＃xff1a;staple &＃61; [10,20,5], drinks &＃61; [5,5,2], x &＃61; 15
输出&＃xff1a;6
解释&＃xff1a;小扣有 6 种购买方案&＃xff0c;所选主食与所选饮料在数组中对应的下标分别是&＃xff1a;
第 1 种方案&＃xff1a;staple[0] &＃43; drinks[0] &＃61; 10 &＃43; 5 &＃61; 15&＃xff1b;
第 2 种方案&＃xff1a;staple[0] &＃43; drinks[1] &＃61; 10 &＃43; 5 &＃61; 15&＃xff1b;
第 3 种方案&＃xff1a;staple[0] &＃43; drinks[2] &＃61; 10 &＃43; 2 &＃61; 12&＃xff1b;
第 4 种方案&＃xff1a;staple[2] &＃43; drinks[0] &＃61; 5 &＃43; 5 &＃61; 10&＃xff1b;
第 5 种方案&＃xff1a;staple[2] &＃43; drinks[1] &＃61; 5 &＃43; 5 &＃61; 10&＃xff1b;
第 6 种方案&＃xff1a;staple[2] &＃43; drinks[2] &＃61; 5 &＃43; 2 &＃61; 7。


示例 2&＃xff1a;

输入&＃xff1a;staple &＃61; [2,1,1], drinks &＃61; [8,9,5,1], x &＃61; 9
输出&＃xff1a;8
解释&＃xff1a;小扣有 8 种购买方案&＃xff0c;所选主食与所选饮料在数组中对应的下标分别是&＃xff1a;
第 1 种方案&＃xff1a;staple[0] &＃43; drinks[2] &＃61; 2 &＃43; 5 &＃61; 7&＃xff1b;
第 2 种方案&＃xff1a;staple[0] &＃43; drinks[3] &＃61; 2 &＃43; 1 &＃61; 3&＃xff1b;
第 3 种方案&＃xff1a;staple[1] &＃43; drinks[0] &＃61; 1 &＃43; 8 &＃61; 9&＃xff1b;
第 4 种方案&＃xff1a;staple[1] &＃43; drinks[2] &＃61; 1 &＃43; 5 &＃61; 6&＃xff1b;
第 5 种方案&＃xff1a;staple[1] &＃43; drinks[3] &＃61; 1 &＃43; 1 &＃61; 2&＃xff1b;
第 6 种方案&＃xff1a;staple[2] &＃43; drinks[0] &＃61; 1 &＃43; 8 &＃61; 9&＃xff1b;
第 7 种方案&＃xff1a;staple[2] &＃43; drinks[2] &＃61; 1 &＃43; 5 &＃61; 6&＃xff1b;
第 8 种方案&＃xff1a;staple[2] &＃43; drinks[3] &＃61; 1 &＃43; 1 &＃61; 2&＃xff1b;


提示&＃xff1a;

1 <&＃61; staple.length <&＃61; 10^5
1 <&＃61; drinks.length <&＃61; 10^5
1 <&＃61; staple[i],drinks[i] <&＃61; 10^5
1 <&＃61; x <&＃61; 2*10^5


来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/2vYnGI

分析

暴力法

直接双层循环&＃xff0c;来遍历就好了

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int i &＃61; 0;
int j &＃61; 0;
int count &＃61; 0;
for(i &＃61; 0; i < stapleSize; i&＃43;&＃43;)

for(j &＃61; 0; j < drinksSize; j&＃43;&＃43;)

if(x >&＃61; staple[i] &＃43; drinks[j])

count&＃43;&＃43;;
count &＃61; count % 1000000007;



return count;



很显然&＃xff0c;结果超时

排序 &＃43; 双指针

其实我们很容易想到先排序&＃xff0c;然后再进行查找后遍历。来优化算法。
这里使用C语言库函数qsort&＃xff0c;时间复杂度为On*log (n)&＃xff0c;我们写的遍历时间复杂度为O(n²)

int compare_int(const void* e1, const void* e2) //比较函数

return *(int*)e1 - *(int*)e2;

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int i &＃61; 0;
int j &＃61; 0;
int count &＃61; 0;
int start &＃61; 0;
int end &＃61; 0;
int mid &＃61; 0;
// 调用库函数 排序函数
qsort(staple, stapleSize, sizeof(staple[0]), compare_int);
qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);
for (i &＃61; 0; i < stapleSize && staple[i] < x; i&＃43;&＃43;)

for(j &＃61; 0; j < drinksSize && drinks[j] <&＃61; x - staple[i]; j&＃43;&＃43;)

count&＃43;&＃43;;
count &＃61; count % 1000000007;


return count;



居然还超时&＃xff0c;我们再想想&＃xff0c;这里我们没有考虑到排序后的数据是有序的特性。接下来我们通过二分法继续优化。

排序 &＃43; 二分法

我们根据staple的值只需要找到drinks数组中临界值。通过drinks的下标就可以一次知道了&＃xff0c;前面都是符合的值&＃xff0c;那么我们就可以用二分法来查找第一个不符合的。但是这里还有一个小坑&＃xff0c;如果所有数据都成立那么通过二分法得到的也仅仅为下标最大值&＃xff0c;所以这里我们可以把所有数据都成立的情况特殊列出来。

这样我们的时间复杂度就是O (log 2 n)与qsort库函数复杂度相同。空间复杂度为1.

int compare_int(const void* e1, const void* e2) //升序排序的比较函数

return *(int*)e1 - *(int*)e2;

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int i &＃61; 0;
int j &＃61; 0;
int count &＃61; 0;
int start &＃61; 0;
int end &＃61; 0;
int mid &＃61; 0;
// 调用库函数 排序函数
qsort(staple, stapleSize, sizeof(staple[0]), compare_int);
qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);
for (i &＃61; 0; i < stapleSize && staple[i] < x; i&＃43;&＃43;)

//考虑到最优情况(特殊情况) 所有数据都符合就直接终止
if (drinks[drinksSize - 1] <&＃61; x - staple[i])

count &＃43;&＃61; drinksSize;
continue;

start &＃61; 0;
end &＃61; drinksSize - 1;
while (start < end)

mid &＃61; (start &＃43; end) / 2;
if (drinks[mid] <&＃61; x - staple[i])

start &＃61; mid &＃43; 1;

else

end &＃61; mid;



count &＃43;&＃61; start;
count &＃61; count % 1000000007;

return count;



功夫不负有心人&＃xff0c;终于能跑了。这里我又想到一个点&＃xff0c;俩个数组的值都是逐渐增大&＃xff0c;而x不变。所以drinks数组的上限end应该小于等于上一个上限。

排序 &＃43; 优化二分法

俩个数组的值都是逐渐增大&＃xff0c;而x不变。所以drinks数组的上限end应该小于等于上一个上限。如果没懂建议多读几遍。所以我们可以再增加一个变量来记录上次的上限用于更新。

int compare_int(const void* e1, const void* e2) //升序排序的比较函数

return *(int*)e1 - *(int*)e2;

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int i &＃61; 0;
int j &＃61; 0;
int count &＃61; 0;
int start &＃61; 0;
int end &＃61; 0;
int mid &＃61; 0;
int upper &＃61; drinksSize - 1; // 用于记录上次所取区间的上限
int len &＃61; 0; // 计算相同价格的主食有几种
// 调用库函数 排序函数
qsort(staple, stapleSize, sizeof(staple[0]), compare_int);
qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);
for (i &＃61; 0; i < stapleSize && staple[i] < x; i&＃43;&＃43;)

// 考虑到最优情况 所有数据都符合就直接终止
if (drinks[drinksSize - 1] <&＃61; x - staple[i])

count &＃43;&＃61; drinksSize;
continue;

// 正常情况
start &＃61; 0;
end &＃61; upper;
mid &＃61; (start &＃43; end) / 2;
while (start < end)

if (drinks[mid] <&＃61; x - staple[i])

start &＃61; mid &＃43; 1;

else

end &＃61; mid;

mid &＃61; (start &＃43; end) / 2;

count &＃43;&＃61; start;
upper &＃61; end;
count &＃61; count % 1000000007;

return count;



排序 &＃43; 二次优化二分法

上面优化了drinks数组&＃xff0c;同样是不是可以优化staple数组&＃xff1f;是的。我们可以将staple相同的数据统计起来一次计算。这里我们又增加了len一个变量&＃xff0c;用来计算staple数组中重复的数据。

int compare_int(const void* e1, const void* e2) //升序排序的比较函数

return *(int*)e1 - *(int*)e2;

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int i &＃61; 0;
int j &＃61; 0;
int count &＃61; 0;
int start &＃61; 0;
int end &＃61; 0;
int mid &＃61; 0;
int upper &＃61; drinksSize - 1; // 用于记录上次所取区间的上限
int len &＃61; 0; // 计算相同价格的主食有几种
// 调用库函数 排序函数
qsort(staple, stapleSize, sizeof(staple[0]), compare_int);
qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);
for (i &＃61; 0; i < stapleSize && staple[i] < x; i&＃43;&＃43;)

len &＃61; 1;
while (i < stapleSize - 1 && staple[i] &＃61;&＃61; staple[i &＃43; 1])

i&＃43;&＃43;;
len&＃43;&＃43;;

// 考虑到最优情况 所有数据都符合就直接终止
if (drinks[drinksSize - 1] <&＃61; x - staple[i])

count &＃43;&＃61; drinksSize * len;
continue;

// 正常情况
start &＃61; 0;
end &＃61; upper;
mid &＃61; (start &＃43; end) / 2;
while (start < end)

if (drinks[mid] <&＃61; x - staple[i])

start &＃61; mid &＃43; 1;

else

end &＃61; mid;

mid &＃61; (start &＃43; end) / 2;

count &＃43;&＃61; start * len;
upper &＃61; end;
count &＃61; count % 1000000007;

return count;



空间换时间&＃xff0c;复杂度直接降为O(n)

因为早餐的价格均为整数&＃xff0c;我们有x的资金。即我们早餐主食的选择有&＃xff1a;1 2 3 … x-1。我们可以用一个n[x]的数组来实现&＃xff0c;数组中存放的是当前下标价位的早餐种类。一次遍历主食staple数组&＃xff0c;获取到符合要求的主食种类。当我们主食价格为2元的搭配都符合时&＃xff0c;那么主食为1元的也不是符合吗&＃xff1f;
所有我们还需要遍历一次&＃xff0c;n[i] &＃43;&＃61; n[i - 1] &＃43; n[i - 2] &＃43; ... n[1];
最后我们只需要对drinks数组遍历&＃xff0c;n[x - drinks[i]]里面存放的值就是当前饮料对应主食的种类。
让我们实现吧。

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)

int n[x];
int i &＃61; 0;
int count &＃61; 0;
memset(n, 0, sizeof(int) * x);
// 将主食价格小于x的放入数组对应的下标&＃xff0c;下标里面放的数字表示当前下标出现的次数
for(i &＃61; 0; i < stapleSize; i&＃43;&＃43;)

if(staple[i] < x)//主食价格小于总金额

n[staple[i]]&＃43;&＃43;;


// 因为前面的价格必然小于等于后面的价格&＃xff0c;也就是只要符合当前下标的话&＃xff0c;你前面也都符合&＃xff0c;
// 所以我们直接累加。假如现在主食8元。n[8]中放的是主食1...8的所有种数
for(i &＃61; 2; i < x; i&＃43;&＃43;)

n[i] &＃43;&＃61; n[i - 1];

for(i &＃61; 0; i < drinksSize; i&＃43;&＃43;)

if(x - drinks[i] > 0)

count &＃43;&＃61; n[x - drinks[i]];
count &＃61; count % 1000000007;


return count;



这样我们的时间复杂度只有O(n),空复杂度也为O(n)

本章完&＃xff01;