您好,欢迎来到飒榕旅游知识分享网。
搜索
您的当前位置:首页算法实验二:微软面试题——关于整数组最小差值的问题。

算法实验二:微软面试题——关于整数组最小差值的问题。

来源:飒榕旅游知识分享网

问题:

 

思路:

解决方案一:最愚笨的办法——暴力穷举,利用数组中所有数据两两相减的对比来求出这个最小差值。

解决方案二:设立辅助数组。以下是设立辅助数组的基本思路

设辅助数组为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)。

 

文章思路引用:

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- sarr.cn 版权所有 赣ICP备2024042794号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务