题目
描述
给一非负整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值.
样例
给出 nums = [3, 1, 7, 1], 返回 1
给出 nums = [2, 1, 2], 返回 2
解答
思路
利用Java的sort()方法排序，从最大的数开始累加，累加和超过总和的一半需要的元素数量，就是所需值。
代码
public class Solution {
/**
* @param arr: an array of non-negative integers
* @return: minimum number of elements
*/
public int minElements(int[] arr) {
// write your code here
List<Integer> nums = new ArrayList<>();
int sum = 0, temp = 0;
for(int num : arr){
sum += num;
nums.add(num);
}
Collections.sort(nums);
int size = nums.size();
for (int i = 1; i < size; i++){
temp += nums.get(size - i);
if(temp > sum / 2) return i;
}
return 0;
}
}
