【每日一题】购买两块巧克力

2023-12-29 09:52:18

Tag

【一次遍历】【数组】【2023-12-29】


题目来源

2706. 购买两块巧克力


解题思路

为了使剩下的钱尽可能的多, 我们需要购买最便宜的两块巧克力。找出最便宜的两块巧克力,有多种方法:

  • 双层枚举找出最便宜的两个巧克力价格之和,时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  • 先排序,后取出价格最小和次小的巧克力,时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
  • 一次遍历找出价格最小和次小的巧克力,时间复杂度为 O ( n ) O(n) O(n)

由于前两种方法过于简单与常规,我们就不赘述了,重点来看一下第三种方法。

方法一:一次遍历

思路

首先维护两个变量,巧克力价格的最小值 minPrice1 和次小值 minPrice2;接着遍历巧克力价格数组:

  • 在遍历的过程中遇到比最小值更小的值,则更新最小值与次小值;
  • 如果当前遍历的值介于最小值和次小值之间,则更新次小值。

最后根据最小值和次小值的和与 money 比较进行返回。

算法

class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        int minPrice1 = INT_MAX, minPrice2 = INT_MAX;
        for (int price : prices) {
            if (price < minPrice1) {
                minPrice2 = minPrice1;
                minPrice1 = price;
            }
            else if (price < minPrice2) {
                minPrice2 = price;
            }
        }
        return minPrice1 + minPrice2 > money ? money : money - minPrice1 - minPrice2;
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135282601
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。