Bir dizide sayı çiftleri arasındaki minimum farkı bulmak için en hızlı algoritma nedir?

Question

Olası Çoğalt:
Is it possible to find two numbers whose difference is minimum in O(n) time

Örneğin

, [4, 2, 7, 11, 8] yılında, algoritma abs(7-8) = 1 dönmelidir.

Kaba kuvvet yolu O (n) olacak ve sıralama O (nlogn) verecektir. Daha verimli bir yolu var mı?

Teşekkür

Answer 1

Sanırım sıralama ve karşılaştırma en iyi bahis olacak. Şunlar gibi:

function minDiff(arr) { 
    var min, 
     temp, 
     initDiff = false, 
     arr = arr.sort(function(a, b){return a-b}), 
     last = arr.length - 1, 
     i; 

    for (i = 0; i < last; i++) { 

     if (!initDiff) {    
      min = arr[i + 1] - arr[i]; 
      initDiff = true; 
     } else {    
      temp = arr[i + 1] - arr[i]; 

      if (temp < min) {    
       min = temp;    
      }    
     } 
    } 

    return min; 
} 

var myArr = [ 1, 8, 5, 96, 20, 47 ], 
    min = minDiff(myArr); 

console.log(min); // 3 

Answer 2

burada Benzer bir soru - Is it possible to find two numbers whose difference is minimum in O(n) time. O (nlogn) gibi görünüyor.

Bu sayfa useful plan bilgilerini de verebilir.