当前位置: 首页 > 面试 > 正文

微软面试题(一)

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
1 using System;
  2 using System.Linq;
  3 using System.Collections.Generic;
  4 namespace ConsoleApplication1
  5 {
  6     class Program
  7     {
  8         static Random Rand = new Random();
  9 
 10         static void Main(string[] args)
 11         {
 12             int count = 10000;
 13             List<int> Input = new List<int>();
 14 //             for (int i = 0; i < count; i++)
 15 //             {
 16 //                 Input.Add(Rand.Next(int.MinValue, int.MaxValue));
 17 //             }
 18             Input.Add(1); Input.Add(2); Input.Add(3); Input.Add(4); Input.Add(5); Input.Add(19);
 19 
 20             ulong re = PigeonNest(Input, ulong.MaxValue);
 21             Console.WriteLine(re);
 22             Console.WriteLine(ulong.MaxValue);
 23             Console.WriteLine(Input.Min());
 24         }
 25 
 26         //鸽巢原理。
 27         static ulong PigeonNest(List<int> List, ulong MinResult)
 28         {
 29             switch (List.Count)
 30             {
 31                 case 0:
 32                 case 1:
 33                     return MinResult;
 34                 case 2:
 35                     return ABS(List[0], List[1]);
 36                 default:
 37                     break;
 38             }
 39             int min = List.Min();
 40             //确定桶的大小。
 41             int width = (int)Math.Ceiling((double)(List.Max() - min) / List.Count);
 42             //不可能比1还小了。
 43             if (width == 1) { return 1ul; }
 44             //把数据丢到桶里。
 45             Dictionary<int, NumbersInfo> EachNestNum = new Dictionary<int, NumbersInfo>();
 46             foreach (int n in List)
 47             {
 48                 int Key = Convert.ToInt32(Math.Ceiling((double)(n - min) / width));
 49                 if (!EachNestNum.ContainsKey(Key))
 50                 {
 51                     EachNestNum.Add(Key, new NumbersInfo(Key));
 52                 }
 53                 EachNestNum[Key].Add(n);
 54             }
 55             //找到所有桶里,和相邻两桶的最大最小值距离,三个数中最近的。
 56             foreach (int Key in EachNestNum.Keys)
 57             {
 58                 MinResult = Min(MinResult, EachNestNum[Key].minresult(EachNestNum, MinResult));
 59             }
 60             return MinResult;
 61         }
 62         class NumbersInfo
 63         {
 64             public NumbersInfo(int k)
 65             { key = k; }
 66             private List<int> List = new List<int>();
 67             private int key;
 68             public int max = int.MinValue;
 69             public int min = int.MaxValue;
 70             public int count { get { return List.Count; } }
 71             public ulong minresult(Dictionary<int, NumbersInfo> EachNestNum, ulong re)
 72             {
 73                 //在三个数中选最小的。  
 74                 //当命中数大于1的时候,递归这个过程。由于迅速收敛,故复杂度忽略不计。
 75                 if (List.Count > 1)
 76                 {
 77                     re = PigeonNest(List, re);
 78                 }
 79                 if (EachNestNum.ContainsKey(key - 1))
 80                 {
 81                     re = Min(ABS(EachNestNum[key].min, EachNestNum[key - 1].max), re);
 82                 }
 83                 if (EachNestNum.ContainsKey(key + 1))
 84                 {
 85                     re = Min(ABS(EachNestNum[key].max, EachNestNum[key + 1].min), re);
 86                 }
 87                 return re;
 88             }
 89             public void Add(int x)
 90             {
 91                 List.Add(x);
 92                 if (x > max) { max = x; }
 93                 if (x < min) { min = x; }
 94             }
 95         }
 96 
 97 
 98         static ulong ABS(int x, int y)
 99         {
100             //三分。
101             switch (x.CompareTo(y))
102             {
103                 case -1:
104                     return (ulong)y - (ulong)x;
105                 case 1:
106                     return (ulong)x - (ulong)y;
107             }
108             return 0ul;
109 
110         }
111 
112         static ulong Min(ulong x, ulong y)
113         {
114             if (x > y) { return y; }
115             return x;
116         }
117     }
118 }

本文固定链接: http://www.chepoo.com/microsoft-interview-one.html | IT技术精华网

【上一篇】
【下一篇】

微软面试题(一):等您坐沙发呢!

发表评论