Рекурсивно удалить все соседние повторяющиеся числа в массиве
Я хочу рекурсивно удалить все соседние повторяющиеся числа в массиве
Я прошел через аналогичные ссылки, где они сделали это на строках
https://www.geeksforgeeks.org/recursively-remove-adjacent-duplicates-given-string/
Ниже приведен код для удаления соседних дубликатов в строке, мне было интересно, есть ли идеальный способ пройти по одним и тем же строкам, но запустить его по массиву
static String removeUtil(String str, char last_removed)
{
// If length of string is 1 or 0
if (str.length() == 0 || str.length() == 1)
return str;
// Remove leftmost same characters and recur for remaining
// string
if (str.charAt(0) == str.charAt(1))
{
last_removed = str.charAt(0);
while (str.length() > 1 && str.charAt(0) == str.charAt(1))
str = str.substring(1, str.length());
str = str.substring(1, str.length());
return removeUtil(str, last_removed);
}
// At this point, the first character is definiotely different
// from its adjacent. Ignore first character and recursively
// remove characters from remaining string
String rem_str = removeUtil(str.substring(1,str.length()), last_removed);
// Check if the first character of the rem_string matches with
// the first character of the original string
if (rem_str.length() != 0 && rem_str.charAt(0) == str.charAt(0))
{
last_removed = str.charAt(0);
return rem_str.substring(1,rem_str.length()); // Remove first character
}
// If remaining string becomes empty and last removed character
// is same as first character of original string. This is needed
// for a string like "acbbcddc"
if (rem_str.length() == 0 && last_removed == str.charAt(0))
return rem_str;
// If the two first characters of str and rem_str don't match,
// append first character of str before the first character of
// rem_str
return (str.charAt(0) + rem_str);
}
Предположим, что входной массив
1) [2,3,3] - вывод [2]
2) [1,2,3,3,2] - [1,2,2] - вывод [1]
3) [2, 0, 0, 2, 3, 3, 0, 0, 1, 1] - вывод []
Изменить. Если кто-то все еще ищет решение, я нашел один выход. Я исправил ошибку в решении @kemalturgul. Это работало на меня.
public static int[] removeUtil(int[] arr)
{
int i=0;
boolean check = false;
for (i = 0; i < arr.length - 1; i++)
{
if (arr[i] == arr[i + 1])
{
check = true;
break;
}
}
if (check)
return removeUtil(combineTwoArray(Arrays.copyOfRange(arr, 0, i), Arrays.copyOfRange(arr, i + 2, arr.length)));
else
return arr;
}
public static int[] combineTwoArray(int[] arr1, int[] arr2) {
int[] newArr = Arrays.copyOf(arr1, arr1.length + arr2.length);
for (int j = 0; j < arr2.length; j++)
newArr[arr1.length + j] = arr2[j];
return newArr;
}
Ответы 5
Вы можете сделать это просто с помощью ArrayDeque.
Просто поместите каждое число из массива в стек, проверьте наличие повторяющихся чисел на каждой итерации в верхней части стека и, если они будут найдены, удалите их.
Да, возможен прямой перевод, при котором вы принимаете int[] вместо String.
Я полагаю, что переводы str.length() и str.charAt(index) тривиальны.
Для str.substring(1, str.length() вам нужен Arrays.copyOfRange(arr, 1, arr.length) (начиная с Java 1.6).
Кроме того, может быть не только один правильный способ «удалить соседние дубликаты». Например:
- [3, 1, 2, 2, 1, 3, 3] → [3, 1, 1, 3, 3] → [3, 1, 1] → [3]
- [3, 1, 2, 2, 1, 3, 3] → [3, 1, 1, 3, 3] → [3, 3, 3] → []
Другой пример:
- [1, 2, 2, 1, 2, 2, 1] → [1, 1, 2, 2, 1] → [1, 1, 1] → []
- [1, 2, 2, 1, 2, 2, 1] → [1, 1, 2, 2, 1] → [2, 2, 1] → [1]
Вот рекурсивное решение:
public static int[] removeUtil(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
System.out.println(Arrays.toString(arr));
return removeUtil(combineTwoArray(Arrays.copyOfRange(arr, 0, i), Arrays.copyOfRange(arr, i + 2, arr.length)));
}
}
return arr;
}
public static int[] combineTwoArray(int[] arr1, int[] arr2) {
int[] newArr = Arrays.copyOf(arr1, arr1.length + arr2.length);
for (int j = 0; j < arr2.length; j++) {
newArr[arr1.length + j] = arr2[j];
}
return newArr;
}
это работает только на итерации
Альтернативное решение, не использующее рекурсию. А использование list вместо String позволит избежать ошибок преобразования (int<->String).
static int [] remover(int [] str){
//List to hold result
List<Integer> l = new ArrayList();
for(int i=0; i<str.length-1; i++){
if (str[i]!=str[i+1])
l.add(str[i]); //keep adjacent distinct value
}
l.add(str[str.length-1]); //add last value
//convert list to array back
return l.stream().mapToInt(Integer::intValue).toArray();
}
public class Main {
public static void main(String[] args) {
System.out.println(Arrays.toString(removeDuplicates(new int[] {2, 0, 0, 2, 3, 3, 0, 0, 1, 1})));
}
public static int[] removeDuplicates(int[] arr) {
int[] stack = new int[arr.length];
int i = 0;
for(int j = 0 ; j < arr.length ; j++) {
int currentNumber = arr[j];
if (i > 0 && stack[i-1] == currentNumber) {
i--;
}else {
stack[i] = currentNumber;
i++;
}
}
return Arrays.copyOfRange(stack , 0 , i);
}
}
Результат программы:
Input is [2,3,3] - output is [2]
input is [1,2,3,3,2] - output is [1]
input is [2, 0, 0, 2, 3, 3, 0, 0, 1, 1] - output is []
Почему вы хотите сделать это рекурсивно, когда итеративный метод было бы проще понять?