问题形容
统计每天不同类型金币的总数。
例如输出：$data = [ ['time'=>'2011-11-04','type'=>1,'gold'=>100], ['time'=>'2011-11-04','type'=>1,'gold'=>200], ['time'=>'2011-11-04','type'=>2,'gold'=>200], ['time'=>'2011-11-04','type'=>2,'gold'=>200]];输入：[ ['time'=>'2011-11-04','type'=>1,'gold'=>300], ['time'=>'2011-11-04','type'=>2,'gold'=>400]]阐明：2011-11-04 号类型为 1 的总金币数为 100 + 200 = 300，同理 2011-11-04 号类型为 2 的总金币数为 200 + 200 = 400 。问题剖析
首先思考什么状况下，两条记录的金币数能相加？
只有当两条记录的 'time' 和 'type' 雷同时能力相加。
实现思路：
判断相邻两条记录的 'time' 和 'type' 是否雷同，如果雷同则更新金币总数，而后持续判断与下一条记录的 'time' 和 'type' 是否雷同。反复这个过程，直到遍历了所有的记录。
参考代码
function solution($data){ $i=0; $re = []; while($i<count($data)){ $j = $i + 1; $total = $data[$i]['gold']; while($j < count($data) && $data[$i]['time'] == $data[$j]['time'] && $data[$i]['type'] == $data[$j]['type']){ $total += $data[$j]['gold']; $j++; } $re[] = [$data[$i]['time'],$data[$i]['type'],$total]; $i = $j; } return $re;}工夫复杂度
尽管代码中有嵌套的二层循环，但每条记录只会扫描一次，因而工夫复杂度为 \(O(n)\)。
相似问题
我写完代码之后发现，这个问题的代码构造与 合并区间算法 的代码构造十分类似。
function merge($arr){ asort($arr); $i = 0; $merged = []; while($i<count($arr)){ $temp = [$arr[$i][0],$arr[$i][1]]; $j = $i + 1; while($j < count($arr) && $temp[1]>=$arr[$j][0]){ $temp[1] = max($temp[1],$arr[$j][1]); $j++; } $merged[] = $temp; $i = $j; } return $merged;}进一步形象：
如果输出是：一个二维数组，并且子数组的某个字段的值是有肯定的程序。例如：统计每天不同类型金币的总数问题中，'time','type' 字段的值是有序的，合并区间问题中，须要先排序。
问题是合并。
解题模板：
- 先找到合并的条件。例如：在统计每天不同类型的金币总数问题中，只有当两条记录的 'time' 和 'type' 雷同时能力合并金币数。
- 判断相邻两条数据是否合并，直到遍历了所有数据。
代码模板：
function solution($data){ $i=0; $re = []; while($i<count($data)){ $j = $i + 1; $temp = $data[$i][...]; // 须要合并的值 while($j < count($data) && condition){ // 更新后果 ... } $re[] = [...];//保留后果 $i = $j; } return $re;}吐槽与心得
这道题是昨天晚上的一个口试的题目，60 分钟 7 道题，5 道选择题，SQL 语句查问和这道算法题算一道大题，最初一道是 无关 Android 的题目，前面没工夫我也没认真看。尽管题量不大，然而选择题不仅要求你选出答案，还要你解释起因。组织语言很费时间，而且考了一道 oc ,一道 Android 的选择题，我一脸懵*。前面做这道算法题的时候还有十几分钟，然而看着工夫一秒一秒流逝，很慌，有一点思路又怕有问题，因为不能调试，纠结来纠结去工夫就没了，还没写完就主动提交了。预计是凉了。不过明天早上花了十几分钟就解决了这个问题，感觉还是不纯熟，没有解题的套路，吃一堑长一智，所以就总结了解决这类问题的模板。