计算数组的最大长度，使得平均值小于给定值

Question

我一直在尝试解决这个问题，但大多数测试用例都会超时。谁能帮我优化一下？

问题陈述：

给定一个长度为 N 的数组 A。你必须从给定的数组 A 中选择一个子集 S，使得 S 的平均值小于 K。你需要打印 S 的最大可能长度。

输入格式：

The first line of each input contains  N, length of array A.
Next line contains N space separated elements of array A.
Next line of input contains an integer Q, Number of queries.
Each following Q  lines contains a single integer K.

输出格式：

For each query, print single integer denoting the maximum possible length of the subset.

示例输入

示例输出

说明

在第一个查询中，没有可能的子集使得其平均值小于 1。
在第二个查询中，您可以select子集{1,2}。
在第三个查询中，您可以select子集{1,2,3,4}。
在第四个和第五个查询中，您可以找到完整的数组{1,2,3,4,5}。

这是我的解决方案：

import java.util.*;

public class Playground {
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        long n = Long.parseLong(s.nextLine());                 // Reading input from STDIN
        String[] temp = s.nextLine().trim().split(" ");
        long[] arr = new long[(int) n];
        for (int i = 0; i < n; i++) 
            arr[i] = Integer.parseInt(temp[i]);
        long q = Long.parseLong(s.nextLine());

        long[] queries = new long[(int) q];
        for (int i = 0; i < q; i++) {
            long x = Long.parseLong(s.nextLine());
            queries[i] = x;
        }
        PriorityQueue<Long> queue = new PriorityQueue<>();
        for (long x : arr)
            queue.add(x);
        for (long x : queries) {
            double avg = 0;
            List<Long> list = new ArrayList<>();
            int i = 0;
            int sum = 0;
            boolean flag = false;
            while (! queue.isEmpty()) {
                long num = queue.poll();
                i++;
                list.add(num);
                sum += num;
                avg = (double) sum / i;

                if (avg >= x) {
                    System.out.println(i - 1);
                    flag = true;
                    break;
                }

            }
            if (! flag)
                System.out.println(n);
            queue.addAll(list);
        }
    }
}

Answer 1

解决这个问题的一个简单方法是先对数组进行排序。
对数组进行排序后，每个元素都等于或大于最后一个，然后求解单个运行很容易：

int count = 0;
int limit = 0;
for (int i : sortedArray) {
    int diff = i - maxAvg;
    if (limit + diff < 0) {
        limit += diff;
        count++
    } else {
        break;
    }
}
System.out.println(count);

这是有效的，因为如果与最大平均值的差异为负，您可以使用具有正差异的值，直到达到限制。

数组排序是O(n*log(n))，对于每个解你只需要O(n)

这是我所有解析的完整解决方案：

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int arrLen = Integer.parseInt(sc.nextLine());
    int[] array = new int[arrLen];
    String[] strNums = sc.nextLine().split(" ", arrLen);
    for (int i = 0; i < arrLen; i++) {
        array[i] = Integer.parseInt(strNums[i]);
    }

    Arrays.sort(array);

    int numTests = Integer.parseInt(sc.nextLine());
    for (int i = 0; i < numTests; i++) {
        int maxAvg = Integer.parseInt(sc.nextLine());
        int limit = 0;
        int count = 0;
        for (int j : array) {
            int diff = j - maxAvg;
            if (limit + diff < 0) {
                count++;
                limit += diff;
            } else {
                break;
            }
        }
        System.out.println(count);
    }
    sc.close();
}

计算数组的最大长度，使得平均值小于给定值

calculate the max length of an array such that average is less than given value

java

algorithm

priority-queue

time-complexity

data-structures