当前位置:首页 > 科技 > 正文

Lintcode 每日一题记录「761」

761 · 最小子集

描述

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

样例

例1:

输入: nums = [3, 1, 7, 1], 输出: 1

例2:

输入: nums = [2, 1, 2], 输出: 2

解答:

class Solution:    """    @param arr:  an array of non-negative integers    @return: minimum number of elements    """    def minElements(self, arr):        # write your code here        arr.sort(reverse=True)        count = sum(arr)        tmp = 0        for i in range(len(arr)):            tmp += arr[i]            count -= arr[i]            if tmp > count:                return i+1
本站文章部分来源于网友投稿或采集自互联网,如有侵权,请联系,本站将及时删除。 另也欢迎广大网友投稿发文!

相关文章:

发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。