如何优化在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 条评论
登录 后参与评论

相关文章

如何使这种方法更通用

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

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

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

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

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

如何使这种方法更简洁?

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

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

在Google路径中的坐标之间插入点的最佳方法是什么?这种方法正确吗?

如何调用函数作为参数,我试过这种方法不起作用?

如何使这种方法可重用?

以这种方式优化我的邮递系统值得吗?

这种方法链接会在C#中被皱眉吗?

这种方法在做什么?(Java)

最大限度。文字行数;这种方法可靠吗?

用这种方法在CSS中创建类是正确的吗?

这种方法线程安全吗?

这种方法超载吗?

MVVM的这种方法会产生内存泄漏吗?

我可以使这种方法更通用/更小吗?(干燥)

我如何在16.04中得到这种外观?

这种方法是异步的吗?

有人可以用这种方法帮助我吗?

如何使这种方法可重用?

Java - 这种方法是多线程的吗?

如何以只需要一种方法(如果可能)的方式优化我的代码?

这种方法如何从 A* 网格中获取节点?

如何在全局使用这种方法?