时间戳

首页 > 解决方案 > 如何降低此任务的代码复杂性？

java - 如何降低此任务的代码复杂性？

问题描述

基本上我有这个任务，我需要根据左边的元素和右边的元素的总和来找到数组的中位数。

如果一个数组是：

1 2 3 4 5

这里的输出应该是 4 ，因为左边的和是 6，右边是 5。

这是解决此任务的代码：

    /**
     * This method calculates the smallest difference and returns it's index.
     *
     * @param array The array being targeted by the method.
     * @return The index of the smallest difference as an integer.
     */
    private static int findSmallestDifference(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int smallestDifferenceIndex = 0;
        int currentDifference = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; ++i) {
            int currentElement = Math.abs(array[i]);
            if (currentElement < currentDifference) {
                smallestDifferenceIndex = i;
                currentDifference = currentElement;
          } else if (currentElement == currentDifference
              && array[i] > 0
              && array[smallestDifferenceIndex] < 0) {
                  smallestDifferenceIndex = i;
          }
        }
        return smallestDifferenceIndex + 1;
    }

    /**
     * This method calculates the left and the right sum of the array.
     *
     * @param array The array being targeted by the method.
     * @return The median of the array as an integer.
     */
    public static int getMedian(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int[] prefix = Arrays.copyOf(array, array.length);
        int[] suffix = Arrays.copyOf(array, array.length);
        int[] difference = new int[array.length];

        for (int i = 1; i < array.length; i++) {
            prefix[i] = prefix[i] + prefix[i - 1];
        }

        for (int i = array.length - 1; i > 0; i--) {
            suffix[i - 1] = suffix[i] + suffix[i - 1];
        }

        for (int i = 0; i < array.length; i++) {
            difference[i] = Math.abs(prefix[i] - suffix[i]);
        }
        return findSmallestDifference(difference);
    }

我的问题是如何简化此解决方案？

标签： java

解决方案

public static int findMedian(int[] arr) {
    int[] leftSum = new int[arr.length];

    for (int i = 0; i < arr.length; i++)
        leftSum[i] = i == 0 ? arr[i] : leftSum[i - 1] + arr[i];

    int rightSum = 0;
    int minDif = Integer.MAX_VALUE;
    int median = 0;

    for (int i = arr.length - 2; i - 1 >= 0; i--) {
        rightSum += arr[i + 1];
        int dif = Math.abs(leftSum[i - 1] - rightSum);

        if (dif < minDif) {
            median = arr[i];
            minDif = dif;
        }
    }

    return median;
}

推荐阅读