OoO
现有一个整型无序数组(较大,百万级),请从中选出一个数,这个数的两边都比它大。
(如果只有一边,满足一边即可。如头和尾的两个数)
这题简单的说,就是尽快求一个局部极小值
1 可用策略
1.0 投机法
对应函数:special
做题首先考虑的肯定是特殊情况
啦!
先往头尾看一看,有没有符合条件的,貌似有75%的概率会中呢!
1.1 二分法
对应函数:binarySearch
二分法可谓是万金油,一般用在有序数组的查找,尤其是数据量很大的时候。
这里虽是无序,但也可以用。
1.2 随缘法
对应函数:guess
随便选个数,看看是否符合条件;如果不符合,继续随机下一个。
这种方法主要看人品。
1.3 可视化法
对应函数:view
可视化法可用在很多地方,优点是化抽象为直观,大大降低理解的门槛。
在这里的用处是:想象这数组是一条高低不平的泥路,扔了一个圆球过去,看它最后滚到哪个坑里。
更具体的,我们还可以选择在哪里扔,扔多少个。
如果往中间扔,扔到一个坡顶,还要考虑往哪边滚,所以倾向于在路两头扔。
也可以扔多个(用gorouting实现),谁先进坑就响一声(往channel发送一个index)。
这里的代码选择扔一个(算法问题就不用多线程了,不然有点作弊的感觉),在开头扔。
1.4 最小值法
对应函数:lessStupid
我找个最小的值,那它两边肯定都是比它大的值了吧?
1.5 笨方法
对应函数:stupid
老实人表示,我一个个看过去不就行了吗?
一点感悟
如果这题让机器来做,它会怎么做?
从上面的策略里选一个?
还是,都记下来,形成决策树,根据情况选择对策? (比如首先肯定看看有没有特殊情况,没有的话再随机挑几个看看,多次不命中就开始用二分法或者滚小球法,一般不会去用剩下的两种苦哈哈的方法)。
那就是说要先把算法装进机器人脑子里?把我们人类智慧的结晶,算法,一样样预装在机器人脑子里, 然后设定个什么情况下来使用,还是
让机器人像人一样会自己思考,在一次次吃亏中总结经验,提高效率?
一开始可能会笨笨的去用简单粗暴低效的方法解决问题,后来可能慢慢的学会了投机取巧
,
手段多了,会见机行事了,不择手段,效率为先。
人体也是一台复杂的机器,非常复杂,但不稳定。 很容易受心情,饮食,环境等因素影响。 而基于硅的二进制体系计算机,则相对稳定得多(24 x 365的服务器了解一下?),虽然好像现在还不够“智能”。
我觉得,未来机器会代替人类做越来越多的事情,而我们要做的,就是如何掌控它们!