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

2020年11月27日 76点热度 0条评论

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

希望该示例可以使您理想地实现自己的目标。如果您有更好的东西,请告诉我。

解决方案如下:

您的解决方案可以使用,但是您可以将解决方案的时间复杂度设为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

注意:原来的两个ArrayLists将被此方法破坏

如果要保留两个数组,建议您跟踪变量列表中列表中的两个索引,然后根据一项小于另一项的时间递增。此外,将whie循环后的If语句检查从isEmpty()检查更改为比较,例如indexOfArrayA == arrayA.size()-1。

希望这对您有所帮助。