рекурсивно находим два элемента с наименьшей разницей в массиве

Question

Я пытаюсь рекурсивно найти два элемента в массиве с наименьшей разницей (предположим, что массив уже отсортирован в порядке возрастания).

Я пытался получить свой код, чтобы просто вернуть наименьшую сумму, но с рекурсией что-то не работает.

public class SmallestDiff { 
    public static void main (String [] args){ 
     int [] x = {1,3,6,9,126}; 
     System.out.println(smallestDiff(x,4)); 
    } 

    public static int smallestDiff (int [] array, int index){ 
     int result; 
     if (index>0){ 
      int diff = Math.abs((array[index]-array[index-1])); 
      result = Math.min (diff, smallestDiff(array,index-1)); 
     } 
     else { 
      return array[0]; 
     } 
     return result; 
    } 
} 

Answer 1

Ваша ошибка состоит в

return array[0]; 

array[0] не разница между значениями так не должны быть возвращены. Самый простой способ исправить программу, чтобы заменить эту строку с

return array[1] - array[0]; 

Answer 2

Попробуйте это:

общественного класса SmallestDiff {

public static void main(String[] args) { 
    int[] x = { 1, 3, 6, 9, 126 }; 

    int result; 
    if (x.length < 2) { 
     result = x[0]; 
    } 
    else{ 
     result = smallestDiff(x, x.length-1); 
    } 
    System.out.println(result); 

} 

public static int smallestDiff(int[] array, int index) { 

    if (index == 0) { 
     return Integer.MAX_VALUE; 

    } 

    int diff = (array[index] - array[index - 1]); 
    return Math.min(diff, smallestDiff(array, index - 1)); 

} 

}

Это решение печатает первый элемент case есть только один элемент в массиве. В противном случае это всегда приведет к наименьшей разнице между двумя элементами.

Answer 3

Если ваш массив отсортирован, нет необходимости в рекурсии. Приведенный ниже код решает проблему с итерацией.

public class SmallestDiff { 

public static void main(String[] args) { 
    int[] x = {1, 3, 6, 9, 126}; 
    System.out.println(smallestDiff(x)); 
} 

public static int smallestDiff(int[] array) { 
    int result = Integer.MAX_VALUE; 
    for (int i = 0; i < array.length - 1; i++) { 
     int diff = Math.abs((array[i] - array[i + 1])); 
     if (diff < result) { 
      result = diff; 
     } 
    } 
    return result; 
} 

}