Last Updated on 2023-12-20 by Clay
題目
You are given an integer array prices representing the prices of various chocolates in a store. You are also given a single integer money, which represents your initial amount of money.
You must buy exactly two chocolates in such a way that you still have some non-negative leftover money. You would like to minimize the sum of the prices of the two chocolates you buy.
Return the amount of money you will have leftover after buying the two chocolates. If there is no way for you to buy two chocolates without ending up in debt, return money. Note that the leftover must be non-negative.
Example 1:Input: prices = [1,2,2], money = 3 Output: 0 Explanation: Purchase the chocolates priced at 1 and 2 units respectively. You will have 3 – 3 = 0 units of money afterwards. Thus, we return 0.
Example 2:Input: prices = [3,2,3], money = 3 Output: 3 Explanation: You cannot buy 2 chocolates without going in debt, so we return 3.
Constraints:
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
解題紀錄
最直覺的方法就是排序，但是這樣最快也是 O(n*log(n))。
所以另一個直覺的作法是依序比較陣列中的元素，遇到比當前最小值還要更小的值時，則更新當前最小值，並將前一個當前最小值放到當前次小值；同時，若是當前的元素比當前最小值大、但是比當前次小值更小，則只需要更新當前次小值即可。
這樣一來，就是 O(n) 的時間複雜度了。
C++ 範例程式碼
class Solution {
public:
int buyChoco(vector<int>& prices, int money) {
// Init
int min1 = INT_MAX;
int min2 = INT_MAX;
// Traversal
for (int& price: prices) {
if (price < min1) {
min2 = min1;
min1 = price;
}
else if (price < min2) {
min2 = price;
}
}
int remaining = money - min1 - min2;
return remaining >= 0 ? remaining : money;
}
};Python 範例程式碼
class Solution:
def buyChoco(self, prices: List[int], money: int) -> int:
# Init
min1 = 101
min2 = 101
# Traversal
for price in prices:
if price < min1:
min2 = min1
min1 = price
elif price < min2:
min2 = price
remaining = money - min1 - min2
return remaining if remaining >= 0 else money