4

我有一个整数数组，我想找到两个最相似的值（最小差异）。

示例：如果数组中的值为 ，则80,100,500,600,501,505最相似的两个值为500和501。我怎样才能做到这一点？

4

4 回答 4

4

这似乎是一项小任务，我们可以将这个问题解决为：

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])
}
于 2012-08-15T18:14:13.633 回答
3

这个问题的诀窍是首先对数组进行排序。这将使您只需要比较彼此相邻的数字；选择差异最小的 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 个最相似的值。

于 2012-08-15T17:38:02.213 回答
2

如果对数据进行排序，时间复杂度为 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
于 2012-08-15T18:22:56.607 回答
0

我将遍历每个元素 O(N^2)。要找到两个最相似的元素，请使用减法并将差异与存储的最低差异进行比较。然后，一旦找到最小的差异（忽略您正在搜索的数字），您还可以存储您正在搜索的数字以及您从中减去的数字。您还应该使用绝对值，以便数字的大小是您所知道的。

于 2012-08-15T17:39:31.363 回答