首页 > 代码库 > 找出排序数组中重复数字的个数

找出排序数组中重复数字的个数

开始我的思路是先二分查找找到一个,然后再两边分别看个数。

但是这种方法会退化到O(n)。效率不好。

 

所以更好的方法是,先找出第一个,再找出最后一个。这个在二分查找的时候,通过判断条件的处理,是能够获得的。

比较基本的思路是,如果找到的数=k,那么判断前面一个数是不是k,如果不是,停止查找,这个是第一个;如果是的,那么继续在前半部分查找。领悟

 

找出排序数组中重复数字的个数