Lintcode:761. 最小子集

描述

给一 非负 整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值.

个人思路：要求取出元素的和大于数组其余元素的和，那么毫无疑问当前的贪心策略应该是优先取出最大的元素。然后比较取出元素的和和生于元素的和，哪一个更大

 public int minElements(int[] arr) {// write your code hereArrays.sort(arr);int[] sumArr = new int[arr.length];int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];sumArr[i] = sum;}int count = 1;int diff = 0;int j = sumArr.length-1;while (diff <= sumArr[j - count]){diff = sumArr[j] - sumArr[j-count];if (diff > sumArr[j - count])break;count++;}return count;}

summary:这里表达每个位置i的和可以不用数组表达，用两个变量就行，感觉用数组鸡肋

dalao写法：

 public int minElements(int[] a) {// write your code hereArrays.sort(a); //数组排序int sum = 0;for(int i=0;i<a.length;i++){ sum+= a[i];}int sumr = 0;int r = 1;for(int i=a.length-1;i>=0;i--){ sumr += a[i];if(sum - sumr > sumr ){r++;}else{break;}}return r;}