面试题整理11 数字在排序数组中出现的次数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题整理11 数字在排序数组中出现的次数,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2468字,纯文字阅读大概需要4分钟。
内容图文
《剑指offer》面试题38:
题目:统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在此数组中出现了4次,因此输出4。
分析:看到排序数组想到二分法解决问题,假设输入数字为k,当中间数大于k时,在前部分查找;当中间数小于k时在后部分查找;当中间数等于k时,前部分和后部分都有可能。
此题之所以记录是因为关键在于中间数等于k时的处理方法的不同和效率的差异比较。
(1)自己写的代码,当中间数等于k时,递归调用前部分、后部分,前面部分k出现的次数+后面部分k出现的次数+1。
int GetNumberOfK1(int* data, int length, int k) { if( data == NULL || length <= 0 ) return 0; return FindKTimes(data,0,length-1,k); } int FindKTimes( int *data, int start, int end,int k) { if( start > end || data[start] > k || data[end] < k ) { return 0; } if( start == end ) { if( data[start] == k ) { return 1; }else { return 0; } } int middle = (start + end)/2; if(data[middle] > k) { return FindKTimes(data,start,middle-1,k); }else if( data[middle] < k ) { return FindKTimes(data,middle+1,end,k); }else { return FindKTimes(data,start,middle-1,k)+ FindKTimes(data,middle+1,end,k)+1; } }
(2)《剑指offer》中代码,采取二分法分别求k第一次和最后一次出现的位置,两者相减+1为总次数。
此种方法相比于自己写的代码的优势在于,当k出现次数多时,递归次数少,极限整个数组都是k时,比(1)效率高很多;当然k没有出现或者出现一两次时递归次数相仿。在求第一次出现时,当中间数等于k时,只递归前面部分;求最后一次时,当中间数等于k时,只求后面部分。
应采用此种方法。
int GetNumberOfK(int* data, int length, int k) { int number = 0; if(data != NULL && length > 0) { int first = GetFirstK(data, length, k, 0, length - 1); int last = GetLastK(data, length, k, 0, length - 1); if(first > -1 && last > -1) number = last - first + 1; } return number; } // 找到数组中第一个k的下标。如果数组中不存在k,返回-1 int GetFirstK(int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start + end) / 2; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0) return middleIndex; else end = middleIndex - 1; } else if(middleData > k) end = middleIndex - 1; else start = middleIndex + 1; return GetFirstK(data, length, k, start, end); } // 找到数组中最后一个k的下标。如果数组中不存在k,返回-1 int GetLastK(int* data, int length, int k, int start, int end) { if(start > end) return -1; int middleIndex = (start + end) / 2; int middleData = data[middleIndex]; if(middleData == k) { if((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length - 1) return middleIndex; else start = middleIndex + 1; } else if(middleData < k) start = middleIndex + 1; else end = middleIndex - 1; return GetLastK(data, length, k, start, end); }
原文:http://blog.csdn.net/kuaile123/article/details/20627659
内容总结
以上是互联网集市为您收集整理的面试题整理11 数字在排序数组中出现的次数全部内容,希望文章能够帮你解决面试题整理11 数字在排序数组中出现的次数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。