java - 如何找到每个过期时间的所有第K个元素

Question

我需要想法或建议来在尽可能短的执行时间内解决以下问题。

输入:

给定一个整数数组 T = [t0, t1, t2, ... tk] 表示一行，其中每个元素都是最大等待时间。一个数组 E = [e0, e1, e2, ... ei] 表示所有可能的过期时间。最后，给出一个整数K，它是容器的最大尺寸。

问题:

对于每个过期时间E，需要获取最后一个能够进入大小K容器的元素T的位置em>，并且每次T中的等待时间必须大于或等于过期时间E才能进入容器。

示例案例 1:

输入:

K = 2； T = [1, 4, 4, 3, 1, 2, 6]; E = [1, 2, 3, 4, 5, 6, 7]

输出:

第 K = [2, 3, 3, 3, 0, 0, 0]

说明:

1. 在E[0]中，过期时间为1，因此行中的第二个T将是最后进入容器的，所以Kth[0] = 2nd;

2. 在E[1]中，过期时间为2，因此行T中的第三个元素将是自第一个元素以来最后进入容器的元素已过期，因此 Kth[1] = 3rd；

3. 在E[2]中，过期时间为3，因此行T中的第三个元素将是自第一个元素以来最后进入容器的元素已过期，因此 Kth[2] = 3rd；

4. 在E[3]中，过期时间为4，因此行T中的第三个元素将是自第一个元素以来最后进入容器的元素已过期，因此 Kth[3] = 3rd；

5. 在 E[4] 中，过期时间为 5，在这种情况下，除了最后一个元素之外，T 中的几乎所有元素都已过期，但是，如下所示无法完成容器，它必须返回位置 0，因此 Kth[4] = 0;

6. E[5] 和 E[6] 依此类推。

解决方案:(高性能)

1. 对于每个元素E，在数组T中搜索大于或等于过期时间E的元素。

2. 统计步骤1中找到的所有元素，如果总数等于K，则最后读取的位置为第K个元素。

3. 对 E 的所有元素重复步骤 1。

public static int[] kth(int k, int[] t, int[] e) {
        int[] kth = new int[e.length];

        if (k > t.length)
            return kth;

        Arrays.sort(e);
        int c = 0;

        for (int i = 0; i < e.length; i++) {            
            for (int j = 0; j < t.length; j++) {
                if (t[j] >= e[i])
                    c++;

                if (c >= k) {
                    kth[i] = j + 1;
                    break;
                }
            }

            if (c < k)
                break;

            c = 0;
        }

        return kth;
}

是否有更快的方法来获取第 k 个元素？ (已解决)

Answer 1

抛开所有“过期时间”和“容器大小”语言，我认为您的问题归结为:

Given integer k and integer lists E and T, find the kth element of T that is larger than or equal to each element of E.

因此，对于特定元素e，Java 代码可能如下所示:

IntStream.range(0, T.size())
    .filter(i -> T[i] >= e).limit(k).max();

据我所知，对于特定元素的算法没有潜在的优化，因为您需要遍历每个元素来过滤它们(尽管此代码可能不是最有效的实现)。

因为您正在计算 E 中的每个元素，所以最明显的优化是缓存结果，这样您就不需要重新计算。例如，您可以缓存满足条件的每个 e 的 k 个索引列表，以便在计算较大的 e 时，您可以首先过滤这些元素，然后在下一个最高元素处重新开始扫描。

我不能保证这是最佳算法(这是您所要求的)。但是，一般来说，实际上不存在这样的事情:算法的效率取决于输入数据。例如，如果 E 中有单个元素，我上面描述的算法将非常低​​效，因为您将存储和计算随后未使用的缓存数据。

作为一个额外的提示，你的最后几行

List<Integer> kth = new ArrayList<>();
for (int i = 0; i < sizeE; i++) {
    kth.add(result[i]);
}
return kth;

最好表示为 return Arrays.asList(result);