MinMax问题实现

Question

问题陈述：

您将得到一个整数、arr和单个整数k的列表，您必须从arr的元素中创建一个长度为k的数组，使其不公平的程度降到最低。打电话给那个阵列潜艇。数组的不公平计算为: max(subarr) - min(subarr)，其中：

• max表示subarr中的最大整数。
• min表示subarr中最小整数。

在下面的编辑器中完成maxMin函数。它必须返回一个整数，该整数表示不公平的最小可能值。

解决方案：

 static int maxMin(int k, int[] arr) {
    int arrLen = arr.length;
    Arrays.sort(arr);
    int[] subArr = Arrays.copyOfRange(arr, 0, k);
    int minUnfairness = subArr[k - 1] - subArr[0];

    for ( int j = 1; j < arrLen - k + 1; j++ ) {

        subArr = Arrays.copyOfRange(arr, j, j+k);

        int tempMinUnfairness = subArr[ k - 1 ] - subArr[0];

        if ( tempMinUnfairness < minUnfairness ) {
            minUnfairness = tempMinUnfairness;
        }
    }

    return  minUnfairness;
 }

  /**
   * Valid Test Case For Reference
   */
   private static void validTest() {
        int[] arr = { 10,100,300,200,1000,20,30 };
        int expected = 20;
        int result = maxMin(3, arr);
        assert (result == expected);
    }

要检查的主要函数是maxMin().

期待着你对-

1. 还能做什么其他的改进？
2. 由于目前的方法是贪婪的，还有什么其他方法可以解决这个问题呢？

谢谢。

Answer 1

你好，欢迎来到代码评审！我对您的解决方案有两个主要关切：

副作用

您的程序在其作用域之外有副作用：Arrays.sort(arr)，当您调用此函数时，您正在对已传递其引用的数组对象进行排序。这意味着要对存在于方法作用域之外的数组进行排序，从而转换传递的任何数组。

由于Arrays.sort()会产生副作用，我建议使用Arrays.copyOf()创建本地副本，然后对本地副本进行排序。

抄袭

在for循环中使用Arrays.copyOf()，这意味着您经常复制和创建新数组。这些内存操作非常昂贵，而且没有必要。

复制一个范围，但只检查范围的结束点。简单地检查否则会成为这些端点的值，难道就不会产生更多的结果吗？本质上，在循环时，维护两个指针，头指针和尾指针(i和i+k-1)，并检查这些值，而不是创建一个新副本。

查看这种方法的一个好方法是:我们基本上保持了k元素的抽象滑动范围，从0开始，我们沿着数组滑动范围，检查每个端点的最小值，而不需要创建具体的副本。

根据以上所述，我将您的解决方案简化如下

static int maxMin(int k, int[] arr) {
    int arrLen = arr.length;
    //1)Make Sorted Local Copy to prevent Side Effects
    int[] localArr = Arrays.copyOf(arr, arrLen);
    Arrays.sort(localArr);

    int minUnfairness = Integer.MAX_VALUE;
    //2)Loop while maintaining two pointers
    // NOTE: we use J instead to prevent side effects on the int k
    int i = 0;
    int j = k - 1;
    while(j < arrLen){
        int tempMinUnfairness = localArr[j] - localArr[i];
        if ( tempMinUnfairness < minUnfairness ) {
            minUnfairness = tempMinUnfairness;
        }
        i++;
        j++;
    }
    return  minUnfairness;
}