java - 配列内で最も類似した2つの値を検索します（Java）

Question

整数の配列があり、最も類似した2つの値（最小の差）を見つけたいと思います。

例：配列の値が、の場合、最も80,100,500,600,501,505類似した2つの値はとです。これどうやってするの？500501

Answer 1

これは小さな作業のようです。この問題は次のように解決できます。

1：効率的な並べ替えアルゴリズムを適用します。

2：次に、隣接する要素を比較し、差が小さいものをピックアップします。

コードはここにあります：

void nearestFinder(){
   int array[];
//apply  sorting algorithm - say selection sort
pre_diff = 0;
new_array = selection_sort(array);
   for(int i =0;i<new_array.length();i++){
      diff = Math.abs(new_array[i]-new_array[i+1]);
      if(diff>pre_diff){
       index =i;
       pre_diff =diff;
       }

      }
print(new_array[index],new_array[index+1])
}

Answer 2

この問題の秘訣は、最初に配列をソートすることです。これにより、互いに隣接している番号を比較するだけで済みます。差が最も小さい2つを選択します。

擬似コード：

sort the array: use Arrays.sort()
 int max_difference = Integer.MAXVALUE
int val1, val2;
for(i=0; i< array_size -1; ++i) {
 int x = array[i+1] - array[i];
 if(x <= max_difference) {
   max_difference = x;
   val1 = array[i];
   val2 = array[i+1];
 }
}

最後に、val1最もval2類似した2つの値が含まれます。

Answer 3

データを並べ替える場合、時間計算量はO（N * ln（N））です。

int[] ints = {80, 100, 500, 600, 501, 505};
Arrays.sort(ints);
int value = 0, delta = Integer.MAX_VALUE;
for (int i = 0; i < ints.length - 1; i++) {
    int d = ints[i + 1] - ints[i];
    if (d < delta) {
        delta = d;
        value = ints[i];
    }
}
System.out.printf("value " + value + " and " + (value + delta));

プリント

value 500 and 501

Answer 4

各要素O（N ^ 2）をループします。最も類似した2つの要素を見つけるには、減算を使用して、保存されている最小の差と差を比較します。次に、最小の差が見つかったら（検索している問題の番号を無視して）、検索している番号とそれを差し引いた番号を保存することもできます。また、絶対値を使用して、数値の大きさが一致するものになるようにする必要があります。