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)。 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的算法--微软面试题：求一个整数数组元素间最小差值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。