Я пытаюсь решить эту проблему CodingBat:
(Это немного более сложная версия проблемы fix34.) Возвращает массив, содержащий точно такие же числа, что и данный массив, но переупорядоченный так, чтобы за каждыми 4 сразу следовала 5. Не перемещайте 4, а все остальные числа может двигаться. Массив содержит одинаковое количество четверок и пятерок, и после каждой четверки стоит число, отличное от 4. В этой версии пятерки могут появляться в любом месте исходного массива.
fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9}
fix45({1, 4, 1, 5}) → {1, 4, 5, 1}
fix45({1, 4, 1, 5, 5, 4, 1}) → {1, 4, 5, 1, 1, 4, 5}
Сначала я использовал метод, который прошел все тесты сайтов, но не думаю, что он сработает для более длинных массивов. Первоначальный метод использовал 2 цикла и не использовал новый массив. Я создал решение, которое вводит новый массив и третий вложенный цикл, и я считаю, что оно будет работать для всех экземпляров проблемы. Однако на сайте указано, что проблемы в этом разделе могут быть решены с помощью двух циклов, поэтому мне интересно, действительно ли существует решение с двумя циклами, которое будет работать для любого случая проблемы. Вот вопрос и мое решение из трех петель:
public int[] fix45(int[] nums) {
int[] locations = {-1};
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == 4) {
JLoop:
for (int j = nums.length-1; j >= 0; --j) {
if (nums[j] == 5) {
for (int k = locations.length-1; k>=0 ; --k) {
if (locations[k] == j) {
continue JLoop;
}
}
nums[j] = nums[i + 1];
nums[i + 1] = 5;
locations[locations.length - 1] = i+1;
locations = java.util.Arrays.copyOf(locations,
locations.length + 1);
locations[locations.length-1] = -1;
break;
}
}
}
}
return nums;
}
Повторный запуск поиска подходящей 5 с одного конца массива каждый раз, когда обнаруживается 4, кажется расточительным. Часть массива уже просканирована и, как известно, не содержит 5, которую можно перемещать. Это время O (n) и пространство O (1).
public static int[] fix45(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == 4 && nums[i + 1] != 5) {
/*
* Need to find the next movable 5 That means an element that is 5 and
* either is the first element or is preceded by anything other than 4
*/
while (nums[j] != 5 || (j != 0 && nums[j - 1] == 4)) {
j++;
}
nums[j] = nums[i + 1];
nums[i + 1] = 5;
}
}
return nums;
}
Эта статья взята из Интернета, укажите источник при перепечатке.
Если есть какие-либо нарушения, пожалуйста, свяжитесь с[email protected] Удалить.
я говорю два предложения