Неправильный результат при попытке получить элемент nth min из несортированного массива в Java
Я пытаюсь получить минимальный элемент nTh из несортированного массива целых чисел. Это то, что я пробовал до сих пор:
private static int nthMin(int[] array, int m) {
int start = 0;
int end = array.length - 1;
int index = 0;
int[] newArray = new int[array.length];
for(int i = 0; i < array.length; i++) {
if (array[i] < array[index]) {
newArray[start] = array[i];
start++;
} else {
newArray[end] = array[i];
end--;
}
//System.out.println(Arrays.toString(newArray));
}
if (m > start) {
return nthMin(Arrays.copyOfRange(newArray, start + 1, newArray.length), m - start);
} else if (m < start) {
return nthMin(Arrays.copyOfRange(newArray, 0, start), m);
} else {
return array[start];
}
}
И я вызываю этот метод, используя:
int[] array = {10, 2, 5, 6, 11, 3, 15};
System.out.println(nthMin(array, 2));
Если попытаться распечатать newArray, я получаю:
[2, 5, 6, 3, 15, 11, 10]
Что, на мой взгляд, правильно. Однако, когда я запускаю весь код, я получаю вторую минуту как 2, но это должен быть 3. Что мне не хватает?
Заранее спасибо!
Ответы 3
вам необходимо использовать алгоритм QuickSelect. Github unnikked / QuickSelect.java
вы можете найти здесь итеративные и рекурсивные решения, которые улучшат ваш код.
Спасибо за этот ресурс. Я взгляну.
Я просто попробовал код и получил тот же результат, что и при использовании своего кода. 2 вместо 3.
Я старался не сильно менять. Теперь цикл for перемещает min и max в начало / конец newArray, а затем переходит к другому вызову метода.
private static int nthMin(int[] array, int m) {
if ((array.length == 1) && (m == 1)) {
return array[0];
}
int start = 0;
int end = array.length - 1;
int[] newArray = new int[array.length];
if (array[0] < array[1]) {
newArray[start] = array[0];
newArray[end] = array[1];
} else {
newArray[start] = array[1];
newArray[end] = array[0];
}
start++;
end--;
for (int i = 2; i < array.length; i++) {
if (array[i] < newArray[0]) {
newArray[start] = newArray[0];
newArray[0] = array[i];
start++;
} else if (array[i] > newArray[array.length - 1]) {
newArray[end] = newArray[array.length - 1];
newArray[array.length - 1] = array[i];
end--;
} else {
newArray[start] = array[i];
start++;
}
System.out.println(Arrays.toString(newArray));
}
if (m == 1) {
return newArray[0];
}
return nthMin(Arrays.copyOfRange(newArray, 1, newArray.length), m - 1);
}
Уау, он работает с рекурсивным вызовом. Спасибо! Не могли бы вы немного объяснить, что вы сделали? Спасибо! Голосовать-уд.
В ПОРЯДКЕ. Я начинаю с рассмотрения простого случая массива из 1 элемента. Далее нужно инициализировать newArray. Поскольку вы хотели получить min и max, я помещаю первые элементы массива в начало и конец newArray (после проверки, какой из них меньше). В цикле for я проверяю, является ли следующий элемент исходного массива меньше, чем первый в newArray, или больше, чем последний в newArray, или иначе. Я поместил этот элемент в подходящее место. После цикла мин и макс должны быть на первом и последнем месте. Затем я проверяю n-1-ю минуту в подмассиве, начиная со второго элемента.
Вы могли бы упростить задачу, если бы не искали max-element. Тебе это не нужно. Имейте в виду, что вы можете искать элемент nth-min в массиве с (n + 1) элементами.
// A function to implement recursive bubble sort
static void bubbleSort(int arr[], int n)
{
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (int i=0; i<n-1; i++)
if (arr[i] > arr[i+1])
{
// swap arr[i], arr[i+1]
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
// Largest element is fixed,
// recur for remaining array
bubbleSort(arr, n-1);
}
// Driver Method
public static void main(String[] args)
{
int arr[] = {2, 5, 6, 3, 15, 11, 10};
bubbleSort(arr, arr.length);
System.out.println("Enter nth Min element you want");
Scanner sc = new Scanner(System.in);
int nth = sc.nextInt();
System.out.println("Nth Min element in your array is: "+arr[nth-1]);
}
Редактировать 1: Я прочитал комментарий и обнаружил, что вы не можете использовать array.sort (), я предлагаю использовать пузырьковую сортировку для сортировки, вы не можете использовать пузырьковую сортировку или это также запрещено?
Изменить 2: Выполняется сортировкой рекурсивный пузырь, подождите.
Спасибо @CommonMan за ваш ответ. К сожалению, мне разрешено использовать только рекурсивный вызов.
подождите, я делаю вашу рекурсивную часть.
можем ли мы использовать рекурсивную пузырьковую сортировку ?? @OlegCaralanski
Нет. Я знаю это решение, но оно не разрешено в моем случае использования.
Это еще один изящный способ. Спасибо! Проголосовал.
Этот код скопирован + вставлен с этого сайта: geeksforgeeks.org/recursive-bubble-sort
Ох .. Он также изменен, обратите внимание, сэр, кроме того, см. Edit 2 ref, да .. просто откровенно отрицательное голосование .. @ Lino
@CommonMan см. редактировать 2 ссылка есть после того, как я опубликовал свой комментарий. Также ваши «изменения» просто изменили код C# на java, который по-прежнему считается копией пасты ИМХО.
@Lino, смотрите основную программу, она скопирована ?? Если вы говорите, что изменение языка по-прежнему является копипастом, то каждый ответ - это ваша копипаста, поскольку они в чем-то похожи на предыдущий. В любом случае, спасибо, что указали. Я не обижен на тебя, добрый день.
@CommonMan Ну, вы даже скопировали + вставили комментарии автора, так что это похоже на простой ответ. Когда вы сравниваете свой ответ с ответом из сообщения в блоге, единственное отличие - это метод swap, которого нет в java. Так что да, я все еще думаю, что это копипаст основной логики, о которой идет речь. Также OP хотел бы улучшить код его и не использовать другое решение
@Lino, спасибо, чувак! Я ценю ваши предложения и буду иметь в виду, что вам лучше, если вы хотя бы указали на ошибку, тогда как другие просто убежат. Кстати, я не использовал функцию sawp, тогда как я реализовал рекурсию пузыря, не знаю, что вы говорите.
@CommonMan Я, как и многие здесь, просто пытаюсь сделать этот сайт лучше, и все делают ошибки. Больше не имеет значения, что у вас есть работающий код, так что это считается
Комментарии не подлежат расширенному обсуждению; этот разговор был переехал в чат.