java - 如何比较数组列表中的每个元素以找到两个数组中第 n 个最小的元素？

Question

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // this section of code will require user input to have the value of n to be set
        System.out.println(("What number would you like to set n equal to ?"));
        Scanner sc = new Scanner(System.in);
        System.out.print(("n= "));
        int value = sc.nextInt();
        System.out.println((""));

        // this section of code set the two array only to hold the value of n
        Random rand = new Random();
        ArrayList<Integer> setA = new ArrayList<Integer>();
        for (int i = 0; i < value; i++) {
            int picks = rand.nextInt(1000);
            setA.add(picks);
        }
        Collections.sort(setA);
        System.out.println(setA);


        ArrayList<Integer> setX = new ArrayList<Integer>();
        for (int k = 0; k < value; k++) {
            int picks = rand.nextInt(1000);
            setX.add(picks);
        }
        Collections.sort(setX);
        System.out.println(setX);
        solution(setA,setX,value);
    }

    private static int solution(ArrayList<Integer> A1, ArrayList<Integer> X1, int value) {
        // This section of code is where the arrays will be compared to find the nth smallest.
        ArrayList<Integer> setF = new ArrayList<Integer>();
        for (int c = 0; c < A1.size(); c++) {
            for(int k = 0; k < X1.size(); k++) {
                if(A1.get(c) < X1.get(k)) {

                }
            }
        }

        System.out.print(setF);
        return value;
    }
}

到目前为止，我已经将程序设置为让用户输入一个将用于数组大小的数字。输入数字后，将使用按顺序放置的随机数字创建数组。接下来，我想遍历数组的每个元素并进行比较，看看哪些数字可以放入我的 Final 数组中。在我的最终数组中，是将返回的第 n 个最小的数字。我无法将两个数组合并在一起。

例如，如果下面的 n = 10 是我的两个数组

A [124, 264, 349, 450, 487, 641, 676, 792, 845, 935]

B [2, 159, 241, 323, 372, 379, 383, 475, 646, 836]

124 < 2 这个语句是错误的，所以 2 将被添加到我的最终数组列表中。数组 B 应移动到列表中的下一个元素。
124 < 159 这是正确的，因此 124 被添加到我的最终数组列表中。数组 A 应移动到列表中的下一个元素。264 < 159 这个说法是错误的，所以 159。

最终数组[2,124, 159,...]

n 最小的是383。

希望这个例子能让您了解我想要实现的目标。如果您有更好的东西，请告诉我..

Answer 1

您的解决方案可行，但您可以使解决方案的时间复杂度为 o(n) 而不是 o(n^2)。

你可以做的是，由于数组是同等排序的，你可以比较位置零处的两个元素(就像你正在做的那样)，然后无论哪个元素较小，从数组中弹出该元素并将其添加到最终的元素大批。继续测试第零个索引元素，直到其中一个数组为空。一旦为空，您可以将剩余的其他数组附加到最终数组的末尾，这样就可以达到您想要的效果。

所以在一些java代码实现中:

private ArrayList<Integer> sortTwoArrays(ArrayList<Integer> arrayA, ArrayList<Integer> arrayB) {
    ArrayList<Integer> finalArray = new ArrayList<>();
    while(!arrayA.isEmpty() && !arrayB.isEmpty()) {
        if (arrayA.get(0) < arrayB.get(0)) {
            // remove element and store
            finalArray.add(arrayA.remove(0));
        }
        else {
            finalArray.add(arrayB.remove(0));
        }
    }

    // Find out which array is not empty
    // Adds remaining contents of non-empty array to end of finalArray
    if (!arrayA.isEmpty()) {
        finalArray.addAll(arrayA);
    }
    else if (!arrayB.isEmpty()) {
        finalArray.addAll(arrayB);
    }

    return finalArray;
}

要获取第 n 个最小值，只需将用户作为参数传入的值添加到函数中，然后在返回函数时，只需返回 finalArray.get(nthIndex)

示例代码展示here .

Note: The original two ArrayLists will get destroyed from this method

If you want preserve the two arrays, I recommend keeping track of both indexes in the list inside variables and then incrementing based on when one item is less than another. Additionally, change the If statement check after the whie-loop from an isEmpty() check to a comparison like so indexOfArrayA == arrayA.size() - 1.

无论如何，我希望这会有所帮助。