今日面试题:数组和

有数组A={5,3,8,9,16},第一次遍历有:A = {3-5,8-3,9-8,16-9}={-2,5,1,7},数组中元素和为-2+5+1+7=11;第二次遍历有:A = {5-(-2),1-5,7-1}={7,-4,6},元素和为9.

给定数组A,求第n次遍历之后,数组中元素的和。

======================================================

此起彼伏分析

原题

有这样一个数组A,大小为n,相邻元素差的绝对值都是1.如: A={4,5,6,5,6,7,8,9,10,9}。 现在,给定A和目标整数t,请找到t在A中的位置。除了依次遍历,还有更好的方法么?

分析

最近有不少的同学反应题目比较简单,还有的同学反应题目有些难,还有的同学的反映很简单:“见过!” 在这里,需要做一下简单的说明:

  • 每天一个题目,确实很难考虑的面面俱到,又要考虑刚刚开始的同学,又要考虑已经比较厉害的同学。所以,只是简单和容易的每天交替着来。

  • 到目前为止,基本都是找的各大公司的面试题,少有原创的面试题。所以,见多识广的同学,肯定是经常有见过的。不过,这个没有关系,温故知新,我相信重新思考,会给大家带来更多的进步。尤其是可以看到更多人的思路,这个带来的进步是巨大的。

  • 我们也希望同学能够多贡献一些高质量的题目。

  • 不会出一些完全是ACM比赛的题目。还是要照顾大多数。

所以,无论题目难易、新旧,只要思考,都会有新的提高。

现在我们来看看今天的题目,今天的题目,最直接的就是遍历,访问每一个元素,并且进行比较。这是任何一个、没有任何特点的数组,都可以采用的方法。也就是,相邻元素差的绝对值,我们没有使用。

那么如何来利用这个特点呢?看下面的数组:

23456545678

如果,我们要找到t=8,则按照如下步骤进行,指针初始指向第一个元素

  • 与第一个元素2比较,差值为6,指针指向第6元素,

  • 当前元素为4,与8比较,差值为4,指针指向第10元素

  • 当前位置为8,找到元素。

为什么可以直接跳跃指到到第6,或者第10个元素呢?原因就是,相邻元素的差的绝对值都是1.这样,针对第一步来说,当前值2与t=8相 差6,如果t在数组中存在,则一定在2的后面第6个以后,而且,只有当2的后面,每一个都是+1的时候,才会在第6个位置找到t。其他的情况,一定都小于 t。

总结下算法过程:

1. 当前元素与t比较,差为0,则找到;

2. 否则,得到差值为k,指针跳到当前元素后的第k个元素。

3. 重复这两步,直到找到t或者t不在数组中。

【分析完毕】

本文来自微信:待字闺中,2013-08-31发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。