思路集

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
矩阵有序，若从左上角向右下角搜索，每次需要考虑向下或向右，不好；若从左下角向右上角搜索，当前数比目标大则向上移，当前数比目标小则向右移，简单快捷。

替换空格

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
如果基于原字符串处理，计算好处理后的长度再从尾向头处理，可以使字符只需要移动一次。
如果基于新空间处理，从头遍历原串，遇到空格就向新串加“%20”，否则加原字符。

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：
当存在某个数字n的个数超过数组大小一半以上时，其他数字与n相抵消后，最终会剩下的数字一定为n。遍历数组，如果计数为0则取记录当前数字并置count为1；如果与记录数字相同则count加1；如果与记录数字不同则count减1。最终count不为0，则再次遍历数组统计n的个数是否大于数组一半。