归并排序应用

Question

归并排序应用

3

我正在做一道练习题，给定一个由N个值组成的数组，需要找到两个数，它们的差（最大值-最小值）是最大的。我希望v大于c...情况是这样的...假设我想以价格C购买拍卖品，这样我就可以以价格V出售它们并获得最大利润，数组的每个单元格都是t日该拍卖品的价格，因此我想以尽可能低的价格购买，以便以最高的价格出售，所以在数组中，C必须出现在V之前。例如：

n = 8
arr = {6,7,3,8,9,2,1,4,20}

我希望得到c = 1和v = 20，因为20 - 1 = 19（这意味着这两个数字的减法结果是最高的）。

另一个例子：

n = 6
arr = {8,12,45,40,18,29}

我想要得到c = 8和v = 45，因为它们的差值是所有其他差值中最大的。(需要澄清的是，c并不总是数组中最小的数)。这两个数字不需要相邻出现。如果我有n = 1, {1}，那么c = 1且v = 1。

这个例子展示了c和v不一定是最小/最大值。

n = 6
arr = {19,27,5,6,7,8}

在这种情况下，c = 19，v = 27。

此外，我需要使用归并排序的代码来解决这个问题。有许多例子将其分为两种方法：mergesort处理递归，而merge则使用辅助数组进行位置交换。

我正在使用归并排序代码（在我看来，合并是不必要的，因为我不关心排序），到目前为止，我有以下代码，但显然是错误的，请问有人能告诉我哪里做错了吗？

public static void mergeSort(int start, int end) {
    if(start < end) {
        int half = (start + end) / 2;
        mergeSort(start, half);
        for(int i = start; start < half; start++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
        mergeSort(half+1, end);
        for(int i = half+1; i < end; half++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
    }
}

非常感谢您能提供的任何帮助！

- Ignacio Pochart

嗨，在第二个例子中，为什么不是8和45？ - fingerman

你不能即兴发明变量！！！temp未定义，arr也是。 - fingerman

@Simeon 是的，这是我的作业，我在递归部分遇到了麻烦。我已经想出了O(n^2)的解法，但我需要它变成O(nlogn)。 - Ignacio Pochart

@fingerman，你说的第二个例子是对的，谢谢。我只粘贴了方法，arr和temp是全局的。 - Ignacio Pochart

@Diogo 我的例子不够好 :S 但在这个练习中，最小值和最大值并不总是最佳选择，数字是由它们之间的差异决定的。 - Ignacio Pochart

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dante May Code · Accepted Answer

我猜测你代码中的mergeSort名称是继承而来的……

既然你已经使用了递归，就没有必要迭代所有元素，因为在递归之后，结果已经呈现出来了。例如，一种可能的方法是将最小值交换到第一个位置，将最大值交换到最后一个位置，然后在递归的“上层”中可以直接检索它们。

这里有另一种解决方案，它利用了归并排序的哲学，但只返回最大值。

public class test {
    static int arr [] = {6,7,3,8,9,2,1,4,20};

    public static void main (String args[]) {
        System.out.println(merge_select_max(0, arr.length - 1));
    }

    public static int merge_select_max (int start, int end) { // both inclusive
        if (start == end) {
            return arr[start];          
        }
        else {
            int half = (start + end) / 2;
            int first = merge_select_max (start, half);
            int second = merge_select_max (half + 1, end);
            return (first > second ? first : second);           
        }       
    }
}