算法--微软面试题：求一个整数数组元素间最小差值

梦里梦外; 2022-06-15 11:06 190阅读 0赞

# Q题目 #

> 有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数.

--------------------

# A解法 #

## 方案一：最愚笨的办法——暴力穷举 ##

利用数组中所有数据两两相减的对比来求出这个最小差值。
    缺点：效率低，浪费资源

**代码如下：**

package 微软数组最小差值;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    /**
     * 有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数
     * @author Administrator
     *
     */
    public class Test1 {
        
        public static void main(String[] args) {
    //      int[] arr={-2,2,5,8,11};
            int[] arr={-2,10,5,87,11,2};
            int min=getMinSubtract(arr);
            System.out.println("==min==="+min);
    
        }
    
        //1.暴力穷举法，求出所有数的差
        public static int getMinSubtract(int[] arr){
            int minus=0;
            //1.若用数组处理，先计算数组长度arr.length的阶乘，因为比较麻烦，这里就不用数组了
            //2.集合处理：存储两数的差值
            ArrayList<Integer> list=new ArrayList<>();
            for(int i=0;i<arr.length-1;i++){
                for(int j=i+1;j<arr.length;j++){
                    minus=Math.abs(arr[i]-arr[j]);
                    list.add(minus);
                }
            }
            System.out.println("所有差值为："+list);
            int min=Collections.min(list);
            return min;
        }
    
    
    }

## 方案二：先排序，再求相邻两个数的差值 ##

**优点：效率高**

**代码如下：**

package 微软数组最小差值;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    
    public class Test2 {
        public static void main(String[] args) {
            int[] arr={-2,10,5,87,11,2};
            int min=getMinSubtract02(arr);
            System.out.println("==min==="+min);
        }
    
        //2.排序后，再求最小值
        public static int getMinSubtract02(int[] arr){
            Arrays.sort(arr);
            System.out.println("排序后的数组："+Arrays.toString(arr));
    
            //这里同样采用集合，不用数组
            ArrayList<Integer> list=new ArrayList<>();
            int start=arr[0];
            for (int i = 1; i < arr.length; i++) {
                int minus=arr[i]-start;//因为数组时按从小到大排序的，所以不用去绝对值
                list.add(minus);
                start=arr[i];
            }
    
            System.out.println("所有差值为："+list);
            int min=Collections.min(list);
            return min;
        }
    }

## 方案三：设立辅助数组（不排序，直接求相邻两个数的差值） ##

**思路分析：**

> 设立辅助数组。以下是设立辅助数组的基本思路
> 
> 设辅助数组为Bn.原来题目中给定的数组是An,则Bn等于：

B1 = A1 - A2;

B2 = A2 - A3;

B3 = A3 - A4;

……

Bn-1 = An-1 - An.

> **注意**，Bn的长度是n-1，正好比An要小一个。聪明的同学看到这个辅助数组，立马就能猜到原因了，因为这样做的话，我们能够把这道看似无从下手求出最优解的问题转化为求Bn的绝对值最小的最长连续子序列和，因为Bn的连续子序列和便是An任意两数之差（注意，由于题目要求的是绝对值最小，所以求出A1-A2等效于得出A2-A1），例如：

A2 - A5 = B2 + B3 + B4 = A2 - A3 + A3 - A4 + A4 - A5 = A2 - A5

实际上，任何Ai - Aj（i<j） = sigma(k=i -> k=j-1)(k)。