手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

【Lintcode】761. Smallest Subset

时间:2021/6/6 4:02:57|来源:|点击: 次

题目地址:

https://www.lintcode.com/problem/761/

给定一个长 n n n的非负整数数组 A A A,要求从其中选出若干数,使得这些数的和大于剩余数的和。问至少要选多少个。

先对 A A A从大到小排序,然后从大到小选数即可。证明可以用调整法,找到第一个没选的数即可。代码如下:

import java.util.Arrays;

public class Solution {
    /**
     * @param A:  an array of non-negative integers
     * @return: minimum number of elements
     */
    public int minElements(int[] A) {
        // write your code here
        Arrays.sort(A);
        int sum = 0;
        for (int i : A) {
            sum += i;
        }
    
        for (int i = A.length - 1, cur = 0; i >= 0; i--) {
            cur += A[i];
            if (cur > sum - cur) {
                return A.length - i;
            }
        }
        
        return 0;
    }
}

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn),空间 O ( 1 ) O(1) O(1)

Copyright © 2002-2019 某某自媒体运营 版权所有