时间戳

首页 > 解决方案 > 如何找到每个过期时间的所有第 K 个元素

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

问题描述

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

输入：

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

问题：

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

示例案例 1：

输入：

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

输出：

Kth = [2, 3, 3, 3, 0, 0, 0]

解释：

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

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

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

  4. 在E[3]中，过期时间为 4，因此第T行中的第 3 个将是第一个元素过期后最后进入容器的，所以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 个元素？（已解决）

标签： javaarraysalgorithmtime-complexity

解决方案

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

给定整数 k 和整数列表 E 和 T，找到 T 的第 k 个大于或等于 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);

推荐阅读