如何优化在Java中这种方法吗?我得到的时间超限

theUturn:

我有两个列表,一个具有元素的索引和其他有股票价格。对于每一个指标我要向上或向下寻找最低,最近股价的股票阵列取其当前索引和最近在比股价更小英寸 这里是我的代码。这是准确的,但过于缓慢,给出了一个时间限制执行错误 ;

public static List<Integer> predictAnswer(List<Integer> stockData, List<Integer> queries) {
    List<Integer> resQuery = new ArrayList<>();

    /* to show -1 if there is no such stock price */
    for (int i = 0; i < queries.size(); i++) {
        resQuery.add(-1);
    }

    for (int i = 0; i < queries.size(); i++) {
        /* the query index starts from 1 or supposes the first index is 1 */
        int index = (int) (queries.get(i) - 1);
        int value = stockData.get(index).intValue();

        int j = index + 1;
        int k = index - 1;

        while (j < stockData.size() - 1 || k > 1) {

            if (k < 1) {
                if (stockData.get(j).intValue() < value) {
                    resQuery.set(i, j + 1);
                    break;
                }
            } 

            else if (j > stockData.size() - 1) {
                if (stockData.get(k).intValue() < value) {
                    resQuery.set(i, k + 1);
                    break;
                }
            } 

            else if (stockData.get(k).intValue() < value) {
                resQuery.set(i, k + 1);
                break;
            } 

            else if (stockData.get(j).intValue() < value) {
                resQuery.set(i, j + 1);
                break;
            }

            j++;
            k--;
        }
    }
}

你能帮助我,以提高性能重构这个代码?

Sarmon:

看来你的算法O(n^2)的时间复杂度。有两种经典的方法来解决这样的问题O(n)第一种使用栈和使用动态编程的第二个。

我建议一个例子来解释什么是不是在你的算法好。

假设你有[1, 4, 3, 2]股票价格。

对于第三个元素3,它会遍历4,然后1找到最近的小向下。

对于最后一个元素2,它会遍历34然后1找到最近的小向下。因此,它并没有考虑到你已经与之前所做的工作 3(它忽略了一个事实,你不必迭代4,因为它是大于3这么大于2)。如果你有很多连续的4,它会遍历所有的人,而不是直接跳跃到1

用动态规划算法的目的是考虑到你以前所做的工作。它使用一个数组来存储所述索引最接近的较小的向下对每个股票价格。与上面的示例中,该阵列的最终版本将是[-1, 0, 0, 0]1不具有最接近的较小向下所以我们用-1表示它,对其他的最接近的较小是1它是在索引0)。

为了计算这个数组,您可以通过初始化[-1, -1, -1, -1]例如,在处理最后一个元素时,你会拥有[-1, 0, 0, -1]你把它比作3,发现3是更大的,所以你直接跳转到最近较小的3这是在指数0你那么你的元素比较索引的元素0(这是1)。1是小,所以你找到最近的小...

你可以做同样的事情为最接近的较小向上。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

来自分类Dev

为什么我不能覆盖蟒蛇这种方法吗?

来自分类Javascript

为什么如果我得到的对象属性在计算对象中变得不确定,而不是对象本身呢?在这种情况下,哪种方法更合适?

来自分类Java

如何重构这种方法?(春天+ Java8)

来自分类Dev

会话集成,这种方法安全吗?

来自分类Java

在Java中,这种方法重载是什么?

来自分类Java

在STS中启动时,我的spring boot应用程序运行正常,但是如果我尝试用jar,这种方法会杀死它吗?

来自分类Java

如何使这种方法更通用

来自分类Dev

如何使这种方法更简洁?

来自分类Java

这种方法是否可能导致死锁?我该如何预防?

来自分类Dev

我如何获得Date(); 在JavaScript中显示时间对吗?

来自分类Dev

如何使用这种方法来获得结果?

来自分类Dev

递归如何在这种方法下工作?

来自分类Dev

为什么Go中没有推广这种方法?

来自分类Dev

在'loop controller',恒定运行时间和'constant timer'中使用无限循环进行Jmeter测试。有什么优点以及如何使用这种方法进行调整

来自分类Java

如何通过Java中的两种方法运行变量

来自分类Dev

我如何在MVC中的post方法之后实现这种重定向

来自分类Java

JDK的这种方法对任何人都有意义吗?

来自分类Java

Android即时功能:这种方法在本质上有缺陷吗?

来自分类Dev

我们可以得到R中的因子矩阵吗?

来自分类Dev

我想知道为什么这种方法无需绑定字符串的内存

来自分类Dev

为什么我不能用这种方法叫道具?(反应)

来自分类Dev

如何异步这种长时间运行的方法?

来自分类Dev

这种方法从何而来

来自分类Java

如何在Java中处理这种打印?

来自分类Java

getISOCountries()方法仅显示两个连续名称。使用这种方法可以获取国家的全名吗?

来自分类Java

我可以在Java中将方法存储在变量中吗?

来自分类Java

我们可以重载Java中的main方法吗?

来自分类Java

我需要在Java中实现继承的方法吗?

来自分类Java

我可以在Java的构造函数中调用方法吗?

TOP 榜单

  1. 1

    来自Microsoft Office加载项taskpane.js的MySQL驱动程序模块的空引用

  2. 2

    HikariPool-1-连接不可用,对于极小的负载服务器,请求在30000ms之后超时

  3. 3

    OpenJDK的和AdoptOpenJDK的区别

  4. 4

    任务':app:minifyReleaseWithR8'.java.lang.NullPointerException的执行失败(无错误消息)

  5. 5

    是什么在Android的consumer-rules.pro和proguard-rules.pro之间的区别?

  6. 6

    java.lang.NoClassDefFoundError:无法初始化类org.bytedeco.javacpp.avutil

  7. 7

    如何优化在Java中这种方法吗?我得到的时间超限

  8. 8

    java.lang.NoSuchFieldError的:ACCEPT_CASE_INSENSITIVE_VALUES

  9. 9

    Keras提前停止回调错误,val_loss指标不可用

  10. 10

    错误TS1086:一个存取器不能在角9的环境上下文被声明

  11. 11

    如何在exoplayer中播放本地媒体文件的硬编码内容uri

  12. 12

    请问Spring事务管理工作与Spring WebFlux?

  13. 13

    在JavaScript中删除多个对象键值

  14. 14

    tensorflow:仅在可用val_acc的情况下可以保存最佳模型,跳过

  15. 15

    未定义:grpc.SupportPackageIsVersion7 grpc.ServiceRegistrar

  16. 16

    在IntelliJ IDEA中并行运行测试用例

  17. 17

    无法装载动态库“libnvinfer.so.6”

  18. 18

    我在android studio中创建了clicker应用。但是,运行时,应用程序在调用“ incrementCount()”后崩溃。为什么?

  19. 19

    Java的无法解析日期的SimpleDateFormat

  20. 20

    如何在Python中将字典拆分成多个字典的列表,所有字典的大小均为N

  21. 21

    如何在“ SQLyog社区版-Mysql GUI”中添加检查约束?

热门标签

归档