Title:Distribute Candies 575
Difficulty:Easy
原题leetcode地址: https://leetcode.com/problems/distribute-candies/
1. 采用set保存糖果种类
时间复杂度:O(n),一次一层循环。
空间复杂度:O(n),申请Set。
/**
* 采用set集合保存糖果的类型
* @param candies
* @return
*/
public static int distributeCandies(int[] candies) {
Set<Integer> set = new HashSet<>();
for (int candy : candies) {
if (!set.contains(candy)) {
set.add(candy);
}
}
return Math.min(set.size(), candies.length / 2);
}
2. 采用排序计算糖果种类
时间复杂度:O(n),一次一层循环。
空间复杂度:O(n),申请Set。
/**
* 先将candies排序,算出种类
* @param candies
* @return
*/
public static int distributeCandies2(int[] candies) {
Arrays.sort(candies);
int count = 1;
for (int i = 1; i < candies.length; i++) {
if (candies[i] != candies[i - 1]) {
count++;
}
}
return Math.min(count, candies.length / 2);
}