Как найти сумму двух элементов в массиве, ближайшем к нулю

Question

Как найти два элемента из массива, сумма которого ближе всего к нулю, но не равна нулю (примечание: -1 ближе всего к нулю, чем +2). это ...

int a[]=new int[n]; 
int b[]=new int[2]; 
int prev=0; 
for(int i=0;i<n;a[i++]=in.nextInt()); 
for(int i=0;i<a.length;i++){ 
    for(int j=i+1;j<a.length;j++){ 
     int sum=a[i]+a[j]; 
     if(prev==0) 
      prev=sum; 
     if(sum > 0){ 
      if(sum < prev){ 
       prev=sum; 
       b[0]=a[i]; 
       b[1]=a[j]; 
      } 
     } 
     else if(sum < 0){ 
      if(-sum < prev){ 
       prev=sum; 
       b[0]=a[i]; 
       b[1]=a[j]; 
      } 
     } 
    } 
} 

    Sop(b[0]+" "+b[1]); 

Answer 1

вы можете попробовать:

int a[]=new int[n]; 
int b[]=new int[2]; 
int prev=0; 
for(int i=0;i<n;a[i++]=in.nextInt()); 
for(int i=0;i<a.length;i++){ 
    for(int j=i+1;j<a.length;j++){ 
     int sum=a[i]+a[j]; 
     if(prev==0) 
      prev=sum; 
     if(Math.abs(sum)>0 && Math.abs(sum)<Math.abs(prev)){ 
      prev=sum; 
      b[0]=a[i]; 
      b[1]=a[j]; 
     } 
    } 
} 

Sop(b[0]+" "+b[1]); 

Answer 2

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

Также у вас есть несколько тестов, чтобы проверить, теперь ли сумма ближе к нулю, чем предыдущая сумма. Однако эти тесты могут быть сведены только к одному, если тест, взяв абсолютное значение суммы вместо тестирования на sum > 0 и sum < 0, что отлично подходит для чтения.

Это то, что я придумал:

int array[] = new int[5]; 
array[0] = -3; array[1] = -2; array[2] = -1; array[3] = 1; array[4] = 2; // Fill array 

int idx[] = new int[2]; // Will store the result (index of the two elements that need to be added) 
double lowest_sum = Double.POSITIVE_INFINITY; // Of type double to be able to use infinity 

for(int i = 0; i < array.length; i++) { 
    // Outer loop --> Uses a current (array[i]) from left to right 
    int current = array[i]; 
    for(int j = i+1; j < array.length; j++) { 
     // Inner loop --> Check all elements we didn't used as current till now 
     int compare_with = array[j]; 
     if((Math.abs(current + compare_with) < lowest_sum) && ((current + compare_with) != 0)) { 
      // We found two elements whose sum is closer to zero 
      lowest_sum = Math.abs(current + compare_with); 
      idx[0] = i; // Index of the first element to add 
      idx[1] = j; // Index of second element to add 
     } 
    } 
} 

int res_idx1 = idx[0]; 
int res_idx2 = idx[1]; 
System.out.println("The first element to add is : " + array[res_idx1] + "\nThe second element to add is : " + array[res_idx2]); 

ввода: массив = [-3, -2, -1, 1, 2], выход: Первый элемент, чтобы добавить это: -3, . Второй элемент для добавления: 2

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

Answer 3

Эта проблема может быть решена в O (N * log (N)). Самая дорогая операция в этом случае будет сортировать ваш массив. Если ваш домен позволяет использовать не сравнительные виды, например counting sort, то вы сможете сократить временную сложность всего решения до линейного времени.

Идея состоит в том, что в отсортированном массиве вы можете последовательно перебирать элементы в восходящем и нисходящем порядке и, следовательно, находить все пары с минимальной/максимальной суммой в линейном времени. Единственным недостатком такого подхода в применении к вашей задаче является то, что вам нужно найти минимальное абсолютное значение суммы, что означает поиск минимума среди положительных сумм и максимума среди отрицательных сумм. Это потребует двух линейных проходов.

Мое решение ниже. Он проверяется на рандомизированных данных против решения грубой силы O (N^2).

// note: mutates argument! 
static Solution solve(int a[]) { 
    Arrays.sort(a); 

    int i = 0; 
    int j = a.length - 1; 

    // -1 indicates uninitialized min value 
    int minI = -1; 
    int minJ = -1; 
    int min = 0; 

    // finding maximal sum among negative sums 
    while (i < j) { 
     int cur = a[i] + a[j]; 
     if (cur != 0 && (minI == -1 || Math.abs(cur) < Math.abs(min))) { 
      min = cur; 
      minI = i; 
      minJ = j; 
     } 

     // if current sum is below zero, increase it 
     // by trying the next, larger element 
     if (cur < 0) { 
      i++; 
     } else { // sum is already non-negative, move to the next element 
      j --; 
     } 
    } 

    i = 0; 
    j = a.length - 1; 
    // finding minimal sum among positive sums 
    while (i < j) { 
     int cur = a[i] + a[j]; 
     if (cur != 0 && (minI == -1 || Math.abs(cur) < Math.abs(min))) { 
      min = cur; 
      minI = i; 
      minJ = j; 
     } 

     if (cur > 0) { 
      j--; 
     } else { 
      i ++; 
     } 
    } 

    if (minI >=0) { 
     return new Solution(minI, minJ, min); 
     //System.out.printf("a[%d]=%d, a[%d]=%d, sum=%d", minI, minJ, a[minI], a[minJ], min); 
    } else { 
     return null; 
     //System.out.println("No solution"); 
    } 
} 

Я просто понял, что сортировка портит показатели, так и minIminJ не будет соответствовать показателям в оригинальном, не отсортированном массиве. Исправление прост - исходный массив должен быть преобразован в массив пар (значение, original_index) перед сортировкой. Хотя я не буду реализовывать это исправление в моем фрагменте примера, так как это еще больше повлияет на читаемость.