July面试题整理系列（1）

题目描述：

给定一个整数数组，要求找到最小的差的绝对值。

思路：

（1）暴力，O(n^2)

（2）O（n*logn），排序+寻找相邻最小的差值的绝对值，实现在下面的fun_1

（3）O（n*logn），分治，最小差值要么在左边要么在右边，或者一个在左边一个在右边，那么第三种情况就分别遍历左右，找到两边最大值和最小值，

最小值之差的绝对值和最大值之差的绝对值中的较小的就是第三种情况的解（未验证）

（4）先哈希映射，然后遍历映射数组，fun_2

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <map>
 8 using namespace std;
 9 
10 
11 vector<int> A;
12 //排序+选择最小相邻元素值
13 int fun_1()
14 {
15     sort(A.begin().A.end());
16     int i;
17     int ans = INT_MAX;
18     for(i = 0 ; i < A.size()-1 ; ++i)
19     {
20         int tmp = abs(A[i]-A[i+1]);
21         ans = min(ans,tmp);
22     }
23     return ans;
24 }
25 //哈希的思想,类似于基数排序
26 int fun_2()
27 {
28     int minNum = INT_MAX;
29     int maxNum = INT_MIN;
30     int i;
31     for(i = 0 ; i < A.size() ; ++i)
32     {
33         minNum = min(minNum,A[i]);
34         maxNum = max(maxNum,A[i]);
35     }
36     vector<int> calNum(maxNum-minNum+1);
37     for(i = 0 ; i < A.size() ; ++i)
38     {
39         calNum[A[i]-minNum]++;
40     }
41     int ans = INT_MAX;
42     bool flag = true;
43     int pre;
44     for(i = 0 ; i < calNum.size(); ++i)
45     {
46         if(calNum[i] >= 2)
47             return 0 ;
48         else if(calNum[i] == 1 && flag)
49         {
50             pre = i;
51             flag = false
52         }
53         else if(calNum[i] == 1 && !flag)
54         {
55             ans = min(ans,i-pre);
56             pre = i;
57         }
58     }
59     return ans;
60 }
61 int main()
62 {
63     return 0;
64 }