java - 合并两个排序数组时，使用数组还是队列更好？

Question

我在一个编程练习网站上工作，该网站要求实现一种合并两个排序数组的方法。这是我的解决方案:

  public static int[] merge(int[] arrLeft, int[] arrRight){
    int[] merged = new int[arrRight.length + arrLeft.length];

    Queue<Integer> leftQueue = new LinkedList<>();
    Queue<Integer> rightQueue = new LinkedList<>();

    for(int i = 0; i < arrLeft.length ; i ++){
        leftQueue.add(arrLeft[i]);
    }

    for(int i = 0; i < arrRight.length; i ++){
        rightQueue.add(arrRight[i]);
    }

    int index = 0;
    while (!leftQueue.isEmpty() || !rightQueue.isEmpty()){

        int largerLeft = leftQueue.isEmpty() ? Integer.MAX_VALUE : leftQueue.peek();
        int largerRight = rightQueue.isEmpty() ? Integer.MAX_VALUE : rightQueue.peek();

        if(largerLeft > largerRight){
            merged[index] = largerRight;
            rightQueue.poll();
        } else{
            merged[index] = largerLeft;
            leftQueue.poll();
        }

        index ++;
    }
    return merged;
   }

但这是官方的解决方案:

public static int[] merge(int[] arrLeft, int[] arrRight){
    // Grab the lengths of the left and right arrays
    int lenLeft = arrLeft.length;
    int lenRight = arrRight.length;
    // Create a new output array with the size = sum of the lengths of left and right
    // arrays
    int[] arrMerged = new int[lenLeft+lenRight];
    // Maintain 3 indices, one for the left array, one for the right and one for 
    // the merged array
    int indLeft = 0, indRight = 0, indMerged = 0;
    // While neither array is empty, run a while loop to merge
    // the smaller of the two elements, starting at the leftmost position of 
    // both arrays
    while(indLeft < lenLeft && indRight < lenRight){
        if(arrLeft[indLeft] < arrRight[indRight])
            arrMerged[indMerged++] = arrLeft[indLeft++];
        else
            arrMerged[indMerged++] = arrRight[indRight++];
    }
    // Another while loop for when the left array still has elements left
    while(indLeft < lenLeft){
        arrMerged[indMerged++] = arrLeft[indLeft++];
    }
    // Another while loop for when the right array still has elements left
    while(indRight < lenRight){
        arrMerged[indMerged++] = arrRight[indRight++];
    }
    return arrMerged;
}

显然，网站上用户的所有其他解决方案也没有使用队列。我想知道使用队列是否效率较低？例如，我会因为在面试中使用队列而受到处罚吗？

Answer 1

由于问题已经指出左右输入数组是排序，这给了你一个提示，你应该能够解决问题而不需要数据输出数组以外的结构。

在真实面试中，面试官很可能会要求您在编写解决方案时讲述您的思考过程。他们可能会声明他们希望在某些约束条件下实现解决方案。在开始编码之前确保问题得到明确定义非常重要。在开始之前问尽可能多的问题，尽可能地限制问题。

完成解决方案实现后，您可以提及实现的时间和空间复杂性，并提出更有效的替代解决方案。

例如，在描述您的实现时，您可以谈论以下内容:

• 创建队列时有开销
• 解决方案的大 O 表示法/时间和空间复杂度
• 在进行任何合并之前，您不必要地遍历左右输入数组的每个元素以创建队列
• 等...

在申请谷歌、微软、亚马逊和一些科技初创公司的职位时，这些类型的面试问题很常见。为了准备此类问题，我建议您解决书籍中的问题，例如 Cracking the Coding Interview .这本书涵盖了如何处理此类问题，以及此类公司的面试过程。