Другой способ получить все комбинации целых чисел массива Javascript

Question

Я хочу перебирать массив и найти все пары, где их разность 2

Это то, что я до сих пор:

var numberOfCases = 5; 
var diff = 2; 

var input = [1,5,3,4,2]; 

getPossiblepairs(input); 

function getPossiblepairs(input){ 
    for(cmp in input){ 
     for(number in input){ 
      if((input[cmp] - input[number]) == diff){ 
       console.log("("+input[cmp]+","+input[number]+")"); 
      } 
     } 

    } 
} 

Этот работает, но я все еще чувствую себя виноватым, используя два для петель, поскольку bigO O (n^2) Это единственный способ сделать это?

Answer 1

Вы можете сделать это в O (n log n). Сортируйте массив, затем пройдите через него за один проход. Найдите разницу между текущим элементом и каждым из следующих двух, распечатав пару, если каждый отличается на 2.

Answer 2

У вас есть память для копии массива? Сначала отсортируйте его, O (n log n), затем выделите пары в одном проходе O (n).

Answer 3

Это должно работать с п лог п сложности:

function getPossiblepairs(input, diff){ 
    // Create a copy of the original array, so it is not affected by the next operation 
    var sortedInput = input.slice(); 
    // Sort the array 
    sortedInput.sort(); 
    // Iterate through the array, starting from the 0th element 
    for (var i=0, n=sortedInput.length; i<n; i++){ 
     firstNumber = sortedInput[i]; 
     // Iterate through the array, starting from the (i+1)th element 
     for (var j=i+1; j<n && sortedInput[j] <= firstNumber + diff; j++){ 
      secondNumber = sortedInput[j]; 
      // if it matches, then log it! 
      if (secondNumber - firstNumber == diff){ 
       console.log('(' + firstNumber + ', ' + secondNumber + ')'); 
      } 
     } 
    } 
} 

См this post для получения дополнительной информации о дублировании массива.

Для использования и тестирования, см: http://jsfiddle.net/gycjup5u/2/

Answer 4

Вы можете использовать indexOf() метод для каждого элемента, чтобы определить, если массив содержит элемент больше, чем по diff:

function getPossiblePairs(input, diff) { 
    for(i in input) { 
     var n = input.indexOf(input[i] + diff); 
     if(n != -1) { 
      console.log("(" + input[i] + "," + input[n] + ")"); 
     } 
    } 
} 

getPossiblePairs(input, diff);