使用数组Java-任何更好的选择

html5 • • 问答

对于以下问题，java 8 中可用的任何更好的选项。

有两个数组，一个整数数组和一个增量数组。将每个增量值应用到整数数组中的元素上，得到每个增量相加后增量元素的绝对值之和。

import java.util.Arrays;

public class ArrayChallenge {

    public static void main(String[] args) {
        long[] nA = {-3, -2, 4, 5};
        long[] iA = {2, 4, -6};
        long[] sumArr = findAbsValueSum(nA, iA);
        System.out.println(Arrays.toString(sumArr));

    }

    public static long[] findAbsValueSum(long[] numArr, long[] incrArr) {
        long[] sumArr = new long[incrArr.length];

        for (int i = 0; i < incrArr.length; i++) {
            long sum = 0;
            for (int j = 0; j < numArr.length; j++) {
                sum = sum + Math.abs(numArr[j] + incrArr[i]);
                numArr[j] = numArr[j] + incrArr[i];
            }
            sumArr[i] = sum;
        }
        return sumArr;
    }
}


Result:
[14, 28, 14]

在 java 8 中是否有更好的选择（性能方面）来做同样的事情？

回答

您粘贴的代码显然与它将获得的效率一样高。计算机不是魔法；如果您发现其他具有sumAll功能的语言或库，它只会在幕后进行。

如果您希望它更有效，则需要设置规则。限制输入或扩大允许做的事情，然后您可以使这更有效。

例如，如果您告诉我这numArr是预先知道的，因此为转换numArr为不同的、更有效的（对于此特定任务）数据类型所做的任何工作都是“免费的”，因为唯一相关的是返回答案一旦incrArr可用，尽快，然后：

  1. 排序numArr到位。（免费 - 可以在不知道 incrArr 的情况下完成）。
  2. 构建一个增量求和数组。该数组是该索引处所有数字的绝对值+所有先前索引的总和；{-3, -2, 4, 5}变成{0, 3, 5, 9, 14}. （免费 - 可以在不知道 incrArr 的情况下完成）

计算正增量的 sumAbs

对于此示例，假设您的增量 ( I) 为2。

  1. 首先，对出现的索引进行二分查找-I；我们将称之为IDX(-I). 这里，IDX(-2)= 1（因为numArr[1]是-2）。如果-I不在列表中，则选择最近的较小数字（如果 -2 不在您的列表中，请改为查找 -3）。（成本：O（logn））。
  2. 对于这个数字，以及numArr该指数以下的所有数字，答案很简单：它是所有这些数字的绝对值之和减去 X*I。这就是O(1)：简直了sumArr[IDX(-I)] - (IDX(-I) * I)。
  3. 接下来找到 0 的索引（成本：O(logn)）。对于所有 0 及以上的数字，答案又是微不足道的。我们首先需要所有正数的总和，即sumArr[sumArr.length - 1] - sumArr[idx(0)]，然后将 X*I 与其中的每个数字相加，类似于我们处理负数的方式。
  4. 这留下了中间有趣的部分，例如-1- 仅对1总和有贡献(-1 + 2 = +1)。没有快速的出路，所以对于输入的这一部分，我们必须遍历它（所以从IDX(-I)到IDX(0)独占，做数学。这在技术上是 O(n)，除了 n受到严重限制；它永远不会更多比I，除非有重复您的列表中（如果有，有一些方法来处理这些散装以及通过使在自由预计算阶段的重阵列），以及通常要少得多;它是重叠：在所有的值介于 0 和 -I 之间的输入。

增量为负

完全相同的算法适用，但相反：对于诸如 的增量-6，0 或以下的所有数字都是微不足道的，所有 6 或更高的数字也是微不足道的。循环只需要覆盖 1 到 5 之间的所有数字，包括 1 和 5。

这导致算法为 O(logn) +O(restricted-n) 而不是您拥有的 O(n) 算法。在纯粹的数学术语中，它仍然是 O(n)，但在几乎所有场景中，它的运算量都少了几个数量级。

构建总和表本身就是 O(n)，所以如果准备时间不是“免费”的，那么这一切都没有意义，而且您所描述的速度会尽可能快。

以上是使用数组Java-任何更好的选择的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>