Как сравнить каждый элемент в моем массиве, чтобы найти 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;
    }
}

Пока у меня настроена программа, чтобы пользователь вводил число, которое будет использоваться для размера массива. После того, как число введено, создаются массивы со случайными числами, которые будут располагаться по порядку. Затем я хотел бы go просмотреть каждый элемент моих массивов и сравнить, какие числа можно поместить в мой массив 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 должен перейти к следующему элементу в списке. <br>124 <159 это верно, поэтому 124 добавляется в мой окончательный список массивов. Массив A должен перейти к следующему элементу в списке. 264 <159 это утверждение неверно, поэтому 159. </p>

Final Array [2,124, 159,...]

n наименьшее - 383.

Надеюсь, этот пример даст вам идеал того, чего я пытаюсь достичь sh .Если у вас есть что-то лучше, дайте мне знать, пожалуйста ..

Answer 1

Ваше решение будет работать, но вы можете сделать сложность времени своего решения o (n), а не o (n ^ 2).

Что вы можете сделать, так как массивы одинаково отсортированы, вы можете сравнить оба элемента в нулевой позиции (как вы делаете), а затем в зависимости от того, какой элемент меньше, извлеките этот элемент из массива и добавьте его в окончательный массив. Продолжайте проверять нулевой (th) индексированный элемент, пока один из массивов не станет пустым. Когда он пуст, вы можете просто добавить оставшийся другой массив в конец окончательного массива, и это должно достичь того, что вы хотите.

Так в некоторой реализации кода 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)

Пример кода showcase здесь .

Примечание. Исходные два списка ArrayList будут уничтожены этим методом

Если вы хотите сохранить два массива, я рекомендую отслеживать оба индекса в списке внутри переменных, а затем увеличиваются в зависимости от того, когда один элемент меньше другого. Кроме того, измените проверку оператора If после wh ie -l oop с проверки isEmpty () на сравнение, подобное таковому indexOfArrayA == arrayA.size () - 1.

I надеюсь, это поможет в любом случае.