Skip to content

Latest commit

 

History

History
149 lines (111 loc) · 3.52 KB

File metadata and controls

149 lines (111 loc) · 3.52 KB

English Version

题目描述

给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。

请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。

你可能有多个相同值的硬币。

 

示例 1:

输入:coins = [1,3]
输出:2
解释:你可以得到以下这些值:
- 0:什么都不取 []
- 1:取 [1]
从 0 开始,你可以构造出 2 个连续整数。

示例 2:

输入:coins = [1,1,1,4]
输出:8
解释:你可以得到以下这些值:
- 0:什么都不取 []
- 1:取 [1]
- 2:取 [1,1]
- 3:取 [1,1,1]
- 4:取 [4]
- 5:取 [4,1]
- 6:取 [4,1,1]
- 7:取 [4,1,1,1]
从 0 开始,你可以构造出 8 个连续整数。

示例 3:

输入:nums = [1,4,10,3,1]
输出:20

 

提示:

  • coins.length == n
  • 1 <= n <= 4 * 104
  • 1 <= coins[i] <= 4 * 104

解法

方法一:排序 + 贪心

我们先对数组进行排序。然后定义 $ans$ 表示当前能够构造的连续整数的个数,初始化为 $1$

遍历数组,对于当前遍历到的元素 $v$,如果 $v \gt ans$,说明无法构造出 $ans+1$ 个连续的整数,因此直接跳出循环,返回 $ans$ 即可。否则,说明可以构造出 $ans+v$ 个连续的整数,因此更新 $ans$$ans+v$

最后返回 $ans$ 即可。

时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 为数组的长度。

Python3

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        ans = 1
        for v in sorted(coins):
            if v > ans:
                break
            ans += v
        return ans

Java

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int ans = 1;
        for (int v : coins) {
            if (v > ans) {
                break;
            }
            ans += v;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int ans = 1;
        for (int& v : coins) {
            if (v > ans) break;
            ans += v;
        }
        return ans;
    }
};

Go

func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins)
	ans := 1
	for _, v := range coins {
		if v > ans {
			break
		}
		ans += v
	}
	return ans
}

...